Advertisement
Guest User

Untitled

a guest
Aug 22nd, 2019
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.75 KB | None | 0 0
  1. //NNSU
  2. #define M7 1000000007
  3. #define M9 1000000009
  4. #define MOD 998244353
  5. #include <iostream>
  6. #include <cctype>
  7. #include <cstring>
  8. #include <cstdio>
  9. #include <fstream>
  10. #include <algorithm>
  11. #include <iterator>
  12. #include <math.h>
  13. #include <cmath>
  14. #include <stdlib.h>
  15. #include <vector>
  16. #include <queue>
  17. #include <stack>
  18. #include <set>
  19. #include <regex>
  20. #include <unordered_set>
  21. #include <string>
  22. #include <map>
  23. #include <iomanip>
  24. #include <sstream>
  25. #include <cassert>
  26. #include <time.h>
  27. #include <numeric>
  28. #include <complex>
  29.  
  30. #define ret return
  31. #define fi first
  32. #define se second
  33. #define X first
  34. #define Y second
  35. #define mp make_pair
  36. #define pu push_back
  37. #define pb push_back
  38. #define all(x) (x).begin(), (x).end()
  39. #define rall(x) (x).rbegin(), (x).rend()
  40. #define sz(x) ((int) (x).size())
  41. #define len(x) ((int) (x).length())
  42. #define rep(i, n) for (int i = 0; i < (n); i++)
  43. #define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
  44. #define tr(x, y) (x)*(x) + (y)*(y)
  45. #define ttr(x, y) (x)*(x) - (y)*(y)
  46. #define re(n) for (int i = 0; i < (n); i++)
  47. #define rej(n) for (int j = 0; j < (n); j++)
  48. #define ren for (int i = 0; i < (n); i++)
  49. #define rejn for (int j = 0; j < (n); j++)
  50. #define read(x) scanf("%d", &x);
  51. #define makeunique(x) sort(all(x)), (x).resize(unique(all(x)) - (x).begin())
  52. #define vpbx v.pu(x);
  53. #define endl '\n'
  54. #define eb emplace_back
  55. #define int long long
  56. #define pi 3.14159265358979
  57. #define rpbx(n) for (int i = 0; i < (n); i++) {int x; cin >> x; v.push_back(x);}
  58.  
  59.  
  60. using namespace std;
  61.  
  62. #define y1 asjgkhasgka
  63. #define y0 aiohgasgas
  64. #define next goas12gisas
  65. #define left goas1232gisas
  66. #define right goasgi315sas
  67. typedef vector<int> vi;
  68. typedef vector<string> vs;
  69. typedef vector<vi> vvi;
  70. typedef pair <int, int> pii;
  71. typedef vector <pii> vii;
  72. typedef long long ll;
  73. typedef vector<ll> vl;
  74. typedef pair <ll, ll> pll;
  75. typedef vector<double> vd;
  76. typedef vector<vl> vvl;
  77. typedef vector<pair<double,double> > vdd;
  78. typedef vector<pll> vll;
  79. typedef long double dbl;
  80. template<class T> T abs(T x) { ret x > 0 ? x : -x; }
  81. template<class T> T gcd(T a, T b) { ret a ? gcd (b % a, a) : b; }
  82. template<class T> T lcm(T a, T b) { ret gcd(a, b) ? (a / gcd(a, b) * b) : 0;}
  83. template<class T> T sqr(T a) { ret a * a; }
  84. template<class T> T sgn(T a) { ret a > 0 ? 1 : (a < 0 ? -1 : 0); }
  85. template<class T1, class T2> pair<T1, T2> operator + (pair<T1, T2> a, pair<T1, T2> b) {a.fi += b.fi; a.se += b.se; ret a;}
  86. template<class T1, class T2> pair<T1, T2> operator - (pair<T1, T2> a, pair<T1, T2> b) {a.fi -= b.fi; a.se -= b.se; ret a;}
  87. template<class T1, class T2> void operator += (pair<T1, T2> &a, pair<T1, T2> b) {a.fi += b.fi; a.se += b.se;}
  88. template<class T1, class T2> void operator *= (pair<T1, T2> &a, pair<T1, T2> b) {a.fi *= b.fi; a.se *= b.se;}
  89. template<class T1, class T2> void operator -= (pair<T1, T2> &a, pair<T1, T2> b) {a.fi -= b.fi; a.se -= b.se;}
  90. // template <char d = ' ', class T> ostream& operator << (ostream& out, vector<T>& v){ for(auto& e : v){ out << e << d; } return out; }
  91. template<class T> ostream& operator<<(ostream &os, const vector<T> &t) { os<<"{"; re(sz(t)- 1) {os<<t[i]<<",";} os<<t[sz(t)-1]; os<<"}"; return os;}
  92. template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
  93.  
  94.  
  95. const dbl EPS = 1e-9;
  96. int n,m,k,cur,pr;
  97. int ans,sum;
  98. int a,b,x,y;
  99.  
  100. vi v;
  101.  
  102.  
  103.  
  104.  
  105.  
  106. set<int> bb, gg;
  107. set<int> lst, rst;
  108. vvi g;
  109. vi vans;
  110. void dfs1(int l){
  111. for(auto o : g[l]){
  112. vans[l] = o - n + 1;
  113. bb.erase(bb.find(l));
  114. gg.erase(gg.find(o - n));
  115. for(auto _ : g[o]) dfs1(_);
  116. }
  117. }
  118. void dfs2(int r){
  119. for(auto o : g[r]){
  120. vans[o] = r - n + 1;
  121. bb.erase(bb.find(o));
  122. gg.erase(gg.find(r - n));
  123. for(auto _ : g[o]) dfs2(_);
  124. }
  125. }
  126. signed main() {
  127. // freopen("lewa.in","r",stdin);
  128. // freopen("output.out", "w", stdout);
  129. ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  130.  
  131.  
  132.  
  133. cin >> n;
  134.  
  135. g.resize(2 * n + 2);
  136. vans.resize(n);
  137. re(n)bb.insert(i), gg.insert(i);
  138. re(n)lst.insert(i), rst.insert(i + n);
  139.  
  140.  
  141.  
  142. re(n){
  143. int x;
  144. cin >> x;
  145. if(!x)continue;
  146. x--;
  147. g[i].pb(x + n);
  148. rst.erase(rst.find(x + n));
  149. }
  150. re(n){
  151. int x;
  152. cin >> x;
  153. if(!x)continue;
  154. x--;
  155. g[i + n].pb(x);
  156. lst.erase(lst.find(x));
  157. }
  158.  
  159.  
  160.  
  161. while(sz(lst)){
  162. int st = *lst.begin();
  163. lst.erase(lst.begin());
  164. dfs1(st);
  165. }
  166.  
  167.  
  168. while(sz(rst)){
  169. int st = *rst.begin();
  170. rst.erase(rst.begin());
  171. dfs2(st);
  172. }
  173.  
  174.  
  175.  
  176.  
  177. while(sz(bb)){
  178. int b = *bb.begin();
  179. bb.erase(bb.begin());
  180. int g = *gg.begin();
  181. gg.erase(gg.begin());
  182. vans[b]= g + 1;
  183. }
  184. re(n) {
  185. assert(vans[i] != 0);
  186. cout << vans[i] << " ";
  187. }
  188. cout << endl;
  189.  
  190.  
  191.  
  192.  
  193.  
  194. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement