fork download 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. #define ll int
  4. #define el "\n"
  5. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6. #define __ROOT__ int main()
  7. #define fi first
  8. #define se second
  9. #define M 1000000007
  10. #define MAXN 30001
  11. #define GIOIHAN 1000001
  12. #define BLOCK_SIZE 425
  13. #define MAX_NODE 1001001
  14. #define LOG 19
  15. #define ALPHA_SIZE 26
  16. #define BASE 311
  17. #define NAME "file"
  18. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); // dùng để nén sort mảng compare
  19. using namespace std;
  20. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  21. const ll NMOD = 1;
  22. const int dx[] = {-1, 0, 1,0};
  23. const int dy[] = {0, 1, 0, -1};
  24. //**Variable**//
  25. ll n, q ;
  26. ll nodeVal[MAXN];
  27. ll high[MAXN] ;
  28. ll chainID[MAXN] ;
  29. ll chainHead[MAXN] ;
  30. ll par[MAXN] ;
  31. ll sz[MAXN] ;
  32. ll tour[MAXN] ;
  33. ll fin[MAXN] ;
  34. ll st[MAXN] ;
  35. ll lab[MAXN] ;
  36. ll visited[MAXN]  ;
  37. vector<ll> adj[MAXN] ;
  38. ll curchain =1, timedfs = 0 ;
  39. //**Struct**//
  40. struct query { // 0 : bridge    , 1 : penguins   , 2 : excursion  ;
  41.     ll t, x,y ;
  42. } que[MAXN * 10 + 2009 ];
  43. struct Seg {
  44.     ll val[MAXN << 2  ] ;
  45.     void build(ll id, ll l, ll r ) {
  46.         if(l == r ) {
  47.             val[id] = nodeVal[tour[l]] ;
  48.         } else {
  49.             ll m = l + r >> 1;
  50.             build(id<< 1, l, m );
  51.             build(id<<1|1, m+ 1, r ) ;
  52.             val[id] = val[id<<1] + val[id<<1|1] ;
  53.         }
  54.     }
  55.     ll get(ll id, ll l, ll r, ll u, ll v ) {
  56.         if(u > r || v < l ) return 0 ;
  57.         if(u <= l && v >= r ) return val[id] ;
  58.         ll m = l + r >> 1;
  59.         return get(id<< 1, l, m, u, v )+ get(id<<1|1, m + 1, r,u, v     ) ;
  60.     }
  61.     void update(ll id, ll l, ll r, ll pos, ll value ) {
  62.         if(l == r ) val[id  ] = value  ;
  63.         else {
  64.             ll m  = l + r >> 1 ;
  65.             if(m >= pos ) update(id<< 1, l, m, pos, value )   ;
  66.             else update(id<<1|1, m + 1, r, pos, value  )  ;
  67.             val[id] = val[id<<1] + val[id<<1|1 ]  ;
  68.         }
  69.     }
  70. } seg ;
  71. //**Function**//
  72. ll LCA(ll u,ll v ) {
  73.     while(chainID[u] != chainID[v]) {
  74.         if(chainID[u] > chainID[v]) u = par[chainHead[chainID[u]]] ;
  75.         else v = par[chainHead[chainID[v]]] ;
  76.     }
  77.     return (high[u] > high[v] ? v : u  );
  78. }
  79. void init() {
  80.     cin>>n;
  81.     for(ll i = 1 ; i <= n ; i ++ ) cin>>nodeVal[i];
  82. }
  83. ll find_set(ll a ) {
  84.     return lab[a] < 0 ? a : lab[a] = find_set(lab[a]) ;
  85. }
  86. bool union_set(ll u, ll v ) {
  87.     u = find_set(u) ;
  88.     v =find_set(v) ;
  89.     if(u == v ) return false;
  90.     if(lab[u] > lab[v]) swap(u, v);
  91.     lab[u] += lab[v] ;
  92.     lab[v] =u  ;
  93.     return true;
  94. }
  95. void dfs(ll u, ll p ) {
  96.     sz[u] = 1 ;
  97.     for(ll v : adj[u]) {
  98.         if(v != p ) {
  99.             high[v] = high[u] + 1 ;
  100.             par[v]= u ;
  101.             dfs(v,  u );
  102.             sz[u] += sz[v] ;
  103.         }
  104.     }
  105. }
  106. void hld(ll u,ll p ) {
  107.     if(!chainHead[curchain]) {
  108.         chainHead[curchain] = u ;
  109.     }
  110.     st[u] = ++ timedfs;
  111.     tour[timedfs] = u ;
  112.     chainID[u] = curchain ;
  113.     ll nxt = 0 ;
  114.     for(ll v : adj[u]) {
  115.         if(v == p ) continue ;
  116.         if( nxt ==0 || sz[v] >sz[nxt] ) nxt = v;
  117.     }
  118.     if(nxt ) {
  119.         hld(nxt,u ) ;
  120.     }
  121.     for(ll v : adj[u]) {
  122.         if(v !=p  && v != nxt) {
  123.             curchain ++ ;
  124.             hld(v,u);
  125.         }
  126.     }
  127.     fin[u] = timedfs ;
  128. }
  129. ll truyvan(ll u,ll v ) {
  130.     ll lca = LCA(u, v), sum = 0  ;
  131.     while(chainID[u] != chainID[lca]) {
  132.         sum += seg.get(1,  1,  n, st[chainHead[chainID[u]]], st[u]) ;
  133.         u = par[chainHead[chainID[u]]] ;
  134.     }
  135.     while(chainID[v] != chainID[lca]) {
  136.         sum += seg.get(1,  1,  n, st[chainHead[chainID[v]]], st[v]) ;
  137.         v = par[chainHead[chainID[v]]] ;
  138.     }
  139.     if(high[u] > high[v] ) swap(u, v) ;
  140.     return sum + seg.get(1, 1, n, st[u], st[v]) ;
  141. }
  142. void prepare() {
  143.     cin>> q ;
  144.     memset(lab, -1, sizeof lab ) ;
  145.     for(ll i = 1 ; i <= q ; i ++ ) {
  146.         string t = "Cảm ơn các bạn đã dành thời gian đọc code của mình, ヾ(≧▽≦*)o , yêu !" ;
  147.         ll x, y ;
  148.         cin>> t >> x >> y;
  149.         if(t[0] == 'b' ) {
  150.             if(union_set(x, y)) {
  151.                 adj[x].push_back(y) ;
  152.                 adj[y].push_back(x) ;
  153.             }
  154.             que[i].t = 0 ;
  155.  
  156.         } else if(t[0] == 'p') {
  157.             que[i].t = 1;
  158.         } else  {
  159.             que[i].t = 2 ;
  160.         }
  161.         que[i].x = x ;
  162.         que[i].y = y ;
  163.     }
  164.     for(ll i = 1; i <= n ; i ++ )if(!sz[i])dfs(i, i );
  165.     memset(lab, -1, sizeof lab ) ;
  166.     for(ll i = 1; i <= n ; i ++ )if(!st[i])hld(i, i  );
  167.     seg.build(1,  1, n  ) ;
  168. }
  169. void solve() {// 0 : bridge    , 1 : update   , 2 : query  ;
  170.     for(ll i = 1 ; i <= q ; i ++ ) {
  171.         ll u = que[i].x, v = que[i].y ;
  172.         if(que[i].t == 0 ) {
  173.             if(!union_set(u, v ) ) cout<< "no" << el ;
  174.             else {
  175.                 cout<<"yes" << el ;
  176.             }
  177.         } else if(que[i].t == 1 ) {
  178.             seg.update(1, 1, n, st[u], v);
  179.         } else {
  180.             if(find_set(u) != find_set(v )) cout<< "impossible" << el ;
  181.             else {
  182.                 cout<<truyvan (u, v  ) << el ;
  183.             }
  184.         }
  185.     }
  186. }
  187.  
  188. __ROOT__ {
  189. //     freopen(NAME".inp" , "r" , stdin);
  190. //     freopen(NAME".out" , "w", stdout) ;
  191.     fast;
  192.     init();
  193.     prepare() ;
  194.     solve();
  195. }
  196.  
Success #stdin #stdout 0.01s 5956KB
comments (?)
stdin 
6
1 2 3 4 5 6
10
bridge 1 2
bridge 2 3
bridge 4 5
excursion 1 3
excursion 1 5
bridge 3 4
excursion 1 5
penguins 3 10
excursion 1 3
bridge 1 5
stdout 
yes
yes
yes
6
impossible
yes
15
13
no
https://ideone.com/QasVWM
language:
C++14 (gcc 8.3)
created:
238 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!