oj.uz

Submission #52596

# Submission time Handle Problem Language Result Execution time Memory
52596 2018-06-26T08:26:16 Z Smelskiy Synchronization (JOI13_synchronization) C++14
100 / 100
 275 ms 15220 KB 
#include <bits/stdc++.h>
using namespace std;




int timer;
int x,y,xx,yy;
int n,m,qq;
int tin[100005];
int tout[100005];
vector<int> v[100005];
int sz;
int res[100005];
int last[100005];
pair<int,int> a[100005];
int cnt[200005];
int t[600006];
int poc[600006];

void dfs(int x,int y) {
    tin[x]=++timer;
    poc[timer]=x;
    for (int i=0;i<v[x].size();++i) {
        int to=v[x][i];
        if (to!=y) dfs(to,x);
    }
    tout[x]=timer;
}

int get(int l,int r,int x,int y) {
    if (t[x]<y || l>y) return -1;
    if (l==r) return poc[l];
    int mid=(l+r)>>1;
    int res=get(mid+1,r,x+x+1,y);
    if (res!=-1) return res;
    return get(l,mid,x+x,y);
}

void update(int x,int y) {
    x+=sz-1;
    t[x]=y;
    x>>=1;
    while (x) {
        t[x]=max(t[x+x],t[x+x+1]);
        x>>=1;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m>>qq;
    for (int i=1;i<n;++i) {
        cin>>x>>y;
        a[i]=make_pair(x,y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    for (int i=1;i<n;++i) {
        x=a[i].first;
        y=a[i].second;
        if (tin[x]>tin[y]) swap(a[i].first,a[i].second);
    }
    sz=1;
    while (sz<n) sz+=sz;
    for (int i=1;i<=n;++i)
        t[sz+i-1]=tout[poc[i]];
    for (int i=sz-1;i>0;--i)
        t[i]=max(t[i+i],t[i+i+1]);
    for (int i=1;i<=n;++i) {
        res[i]=1;
    }
    for (int i=1;i<=m;++i) {
        cin>>xx;
        x=a[xx].first;
        y=a[xx].second;
        yy=get(1,sz,1,tin[x]);
        cnt[xx]^=1;
        if (cnt[xx]) {
            res[yy]+=res[y]-last[y];
            update(tin[y],0);
        } else {
            res[y]=last[y]=res[yy];
            update(tin[y],tout[y]);
        }
    }
    while (qq--) {
        cin>>x;
        x=get(1,sz,1,tin[x]);
        cout<<res[x]<<'\n';
    }

}

Compilation message

synchronization.cpp: In function 'void dfs(int, int)':
synchronization.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();++i) {
                  ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2796 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 4 ms 2796 KB Output is correct
5 Correct 4 ms 2872 KB Output is correct
6 Correct 6 ms 2908 KB Output is correct
7 Correct 18 ms 3624 KB Output is correct
8 Correct 19 ms 3652 KB Output is correct
9 Correct 15 ms 3724 KB Output is correct
10 Correct 190 ms 10308 KB Output is correct
11 Correct 170 ms 10308 KB Output is correct
12 Correct 133 ms 14840 KB Output is correct
13 Correct 119 ms 14840 KB Output is correct
14 Correct 104 ms 14840 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 14840 KB Output is correct
2 Correct 104 ms 14840 KB Output is correct
3 Correct 79 ms 14840 KB Output is correct
4 Correct 78 ms 14840 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14840 KB Output is correct
2 Correct 4 ms 14840 KB Output is correct
3 Correct 4 ms 14840 KB Output is correct
4 Correct 4 ms 14840 KB Output is correct
5 Correct 4 ms 14840 KB Output is correct
6 Correct 5 ms 14840 KB Output is correct
7 Correct 17 ms 14840 KB Output is correct
8 Correct 219 ms 15036 KB Output is correct
9 Correct 163 ms 15036 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 15220 KB Output is correct
2 Correct 128 ms 15220 KB Output is correct
3 Correct 113 ms 15220 KB Output is correct
4 Correct 110 ms 15220 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15220 KB Output is correct
2 Correct 4 ms 15220 KB Output is correct
3 Correct 4 ms 15220 KB Output is correct
4 Correct 4 ms 15220 KB Output is correct
5 Correct 5 ms 15220 KB Output is correct
6 Correct 18 ms 15220 KB Output is correct
7 Correct 250 ms 15220 KB Output is correct
8 Correct 275 ms 15220 KB Output is correct
9 Correct 179 ms 15220 KB Output is correct
10 Correct 177 ms 15220 KB Output is correct
11 Correct 125 ms 15220 KB Output is correct
12 Correct 168 ms 15220 KB Output is correct
13 Correct 108 ms 15220 KB Output is correct