oj.uz

Submission #416299

# Submission time Handle Problem Language Result Execution time Memory
416299 2021-06-02T09:33:40 Z MarcoMeijer Synchronization (JOI13_synchronization) C++14
50 / 100
 789 ms 44992 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]);
  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[b[d[i]]]] ? up : hd[b[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]] = !exist[d[i]];
  }

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23964 KB Output is correct
2 Incorrect 14 ms 23884 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 37572 KB Output is correct
2 Correct 385 ms 37280 KB Output is correct
3 Correct 315 ms 43616 KB Output is correct
4 Correct 306 ms 43588 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23884 KB Output is correct
2 Correct 14 ms 23884 KB Output is correct
3 Correct 14 ms 23884 KB Output is correct
4 Correct 15 ms 23984 KB Output is correct
5 Correct 15 ms 23884 KB Output is correct
6 Correct 20 ms 24184 KB Output is correct
7 Correct 78 ms 26060 KB Output is correct
8 Correct 789 ms 44992 KB Output is correct
9 Correct 737 ms 44908 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 44968 KB Output is correct
2 Correct 526 ms 44376 KB Output is correct
3 Correct 534 ms 44600 KB Output is correct
4 Correct 539 ms 44552 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23884 KB Output is correct
2 Correct 14 ms 23952 KB Output is correct
3 Correct 14 ms 23884 KB Output is correct
4 Incorrect 15 ms 23996 KB Output isn't correct
5 Halted 0 ms 0 KB -