oj.uz

Submission #416324

# Submission time Handle Problem Language Result Execution time Memory
416324 2021-06-02T10:19:49 Z MarcoMeijer Synchronization (JOI13_synchronization) C++14
100 / 100
 866 ms 47712 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define all(a) a.begin(),a.end()
#define fi first
#define se second

const int INF	= 1e9;
const int MX	= 5e5;
const int N	= 1<<20;
const int MOD	= 1e9+7;

int n, m, q;
int a[MX], b[MX], c[MX], d[MX];

// tree stuff
vi adj[MX], chl[MX];
int par[MX], siz[MX], dep[MX];
void dfs(int u, int p) {
  par[u] = p;
  siz[u] = 1;
  dep[u] = dep[p] + 1;
  FOR(v,adj[u]) {
    if(v == p) continue;
    siz[u] += siz[v];
    dfs(v,u);
    chl[u].pb(v);
  }
}

// seg
struct Seg{
  int seg[N*2];

  void setSeg(int i, int j, int v, int lazy=0, int p=1, int l=0, int r=N-1) {
    if(lazy) seg[p] = lazy;
    if(j < l || i > r) return;
    if(i <= l && j >= r) {
      seg[p] = v;
      return;
    }
    int m=(l+r)/2;
    setSeg(i,j,v,seg[p],p*2,l,m);
    setSeg(i,j,v,seg[p],p*2+1,m+1,r);
    seg[p] = 0;
  }
  int getSeg(int i, int lazy=0, int p=1, int l=0, int r=N-1) {
    if(lazy) seg[p] = lazy;
    if(i < l || i > r) return 0;
    if(l == r) return seg[p];
    int m=(l+r)/2;
    int a=getSeg(i,seg[p],p*2,l,m);
    int b=getSeg(i,seg[p],p*2+1,m+1,r);
    seg[p] = 0;
    return a+b;
  }
} upseg, downseg;

// hld
int hd[MX], segi[MX], curseg=0;
void hld(int u, int head) {
  hd[u] = head;
  segi[u] = curseg++;
  if(chl[u].empty()) return;
  int bst=chl[u][0];
  FOR(v,chl[u]) if(siz[v] > siz[bst]) bst = v;
  hld(bst,head);
  FOR(v,chl[u]) if(bst != v) hld(v,v);
}
int getRoot(int u) {
  while(true) {
    int nu = upseg.getSeg(segi[u]);
    if(nu == u) break;
    u = nu;
  }
  return u;
}

// problem specific
int edge[MX], vert[MX], exist[MX];
int getVal(int u) {
  return vert[getRoot(u)];
}

int main() {
  // input
  cin>>n>>m>>q;
  RE1(i,n-1) cin>>a[i]>>b[i];
  RE1(i,m) cin>>d[i];
  RE1(i,q) cin>>c[i];

  RE1(i,n-1) adj[a[i]].pb(b[i]);
  RE1(i,n-1) adj[b[i]].pb(a[i]);
  dfs(1,1);
  hld(1,1);
  RE1(i,n-1) if(a[i] != par[b[i]]) swap(a[i], b[i]);
  RE1(i,n) downseg.setSeg(segi[i],segi[i],i);
  RE1(i,n) upseg  .setSeg(segi[i],segi[i],i);
  RE1(i,n) vert[i] = 1;

  RE1(i,m) {
    if(!exist[d[i]]) {
      int nval = getVal(a[d[i]]) + getVal(b[d[i]]) - edge[d[i]];
      int down = downseg.getSeg(segi[b[d[i]]]);
      if(hd[a[d[i]]] != hd[b[d[i]]]) {
        // d[i] is not a heavy edge
        upseg  .setSeg(segi[b[d[i]]], segi[down], a[d[i]]);
      } else {
        // d[i] is a heavy edge
        int up = upseg.getSeg(segi[a[d[i]]]);
        int rt = dep[up] > dep[hd[a[d[i]]]] ? up : hd[a[d[i]]];
        upseg  .setSeg(segi[rt], segi[down], up);
        downseg.setSeg(segi[rt], segi[down], down);
      }
      vert[getRoot(a[d[i]])] = nval;
    }
    else {
      edge[d[i]] = vert[b[d[i]]] = getVal(a[d[i]]);
      int down = downseg.getSeg(segi[b[d[i]]]);
      upseg.setSeg(segi[b[d[i]]], segi[down], b[d[i]]);
      if(hd[a[d[i]]] == hd[b[d[i]]]) {
        // d[i] is a heavy edge
        int up = upseg.getSeg(segi[a[d[i]]]);
        int rt = dep[up] > dep[hd[a[d[i]]]] ? up : hd[a[d[i]]];
        downseg.setSeg(segi[rt], segi[a[d[i]]], a[d[i]]);
      }
    }
    exist[d[i]] ^= 1;
  }

  RE1(i,q) {
    cout << getVal(c[i]) << endl;
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23884 KB Output is correct
2 Correct 15 ms 23888 KB Output is correct
3 Correct 15 ms 23916 KB Output is correct
4 Correct 15 ms 23968 KB Output is correct
5 Correct 15 ms 23920 KB Output is correct
6 Correct 19 ms 24056 KB Output is correct
7 Correct 59 ms 25280 KB Output is correct
8 Correct 57 ms 25280 KB Output is correct
9 Correct 59 ms 25252 KB Output is correct
10 Correct 572 ms 37308 KB Output is correct
11 Correct 533 ms 37492 KB Output is correct
12 Correct 543 ms 46636 KB Output is correct
13 Correct 401 ms 36096 KB Output is correct
14 Correct 424 ms 36044 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 39108 KB Output is correct
2 Correct 403 ms 38852 KB Output is correct
3 Correct 325 ms 43544 KB Output is correct
4 Correct 318 ms 43524 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23924 KB Output is correct
2 Correct 15 ms 23884 KB Output is correct
3 Correct 15 ms 23956 KB Output is correct
4 Correct 16 ms 23976 KB Output is correct
5 Correct 16 ms 23980 KB Output is correct
6 Correct 22 ms 24184 KB Output is correct
7 Correct 85 ms 26048 KB Output is correct
8 Correct 773 ms 44836 KB Output is correct
9 Correct 758 ms 44864 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 749 ms 44860 KB Output is correct
2 Correct 542 ms 44428 KB Output is correct
3 Correct 544 ms 44548 KB Output is correct
4 Correct 548 ms 44552 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23884 KB Output is correct
2 Correct 14 ms 23884 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 16 ms 23884 KB Output is correct
5 Correct 21 ms 24060 KB Output is correct
6 Correct 80 ms 25288 KB Output is correct
7 Correct 774 ms 38724 KB Output is correct
8 Correct 866 ms 47712 KB Output is correct
9 Correct 570 ms 37752 KB Output is correct
10 Correct 858 ms 37736 KB Output is correct
11 Correct 653 ms 42584 KB Output is correct
12 Correct 621 ms 42628 KB Output is correct
13 Correct 546 ms 46852 KB Output is correct