oj.uz

Submission #52198

# Submission time Handle Problem Language Result Execution time Memory
52198 2018-06-24T19:54:22 Z Smelskiy Synchronization (JOI13_synchronization) C++14
50 / 100
 489 ms 32788 KB 
#include <bits/stdc++.h>
using namespace std;



int n,m,qq;
int ans;
vector<pair<int,int> > v[200005];
int f[200005];
int last[200005];
int c[200005];
int x,y;

void dfs(int x,int y,int xx,int yy) {
    if (xx<=yy) ++ans;
    for (int i=0;i<v[x].size();++i) {
        int to=v[x][i].first;
        if (to==y) continue;
        int xx2;
        int yy2=min(yy,last[v[x][i].second]);
        xx2=f[v[x][i].second];
        dfs(to,x,xx2,yy2);
    }
}



set<pair<int,int> > s;
pair<int,int> q[500005];
pair<int,int> t[500005];
int sz;
pair<int,int> ans2[500005];

inline void push(int x) {
    q[x+x].first=min(q[x+x].first,q[x].first);
    q[x+x+1].first=min(q[x+x+1].first,q[x].first);
    t[x+x].first=min(t[x+x].first,q[x].first);
    t[x+x+1].first=min(t[x+x+1].first,q[x].first);
    q[x+x].second=max(q[x+x].second,q[x].second);
    q[x+x+1].second=max(q[x+x+1].second,q[x].second);
    t[x+x].second=max(t[x+x].second,q[x].second);
    t[x+x+1].second=max(t[x+x+1].second,q[x].second);
}

void update(int l,int r,int ll,int rr,int x,int y,int z) {
    if (l>r || ll>r || l>rr || ll>rr) return;
    if (l>=ll && r<=rr) {
        q[x].first=min(q[x].first,y);
        q[x].second=max(q[x].second,z);
        t[x].first=min(t[x].first,y);
        t[x].second=max(t[x].second,z);
        return;
    }
    push(x);
    int mid=(l+r)>>1;
    update(l,mid,ll,rr,x+x,y,z);
    update(mid+1,r,ll,rr,x+x+1,y,z);
    t[x].first=min(t[x+x].first,t[x+x+1].first);
    t[x].second=max(t[x+x].second,t[x+x+1].second);
}

pair<int,int> get(int l,int r,int ll,int rr,int x) {
    if (l>r || l>rr || ll>r || ll>rr) return make_pair(1e9,-1e9);
    if (l>=ll && r<=rr) return t[x];
    push(x);
    int mid=(l+r)>>1;
    pair<int,int> res=get(l,mid,ll,rr,x+x);
    pair<int,int> res2=get(mid+1,r,ll,rr,x+x+1);
    res.first=min(res.first,res2.first);
    res.second=max(res.second,res2.second);
    return res;
}

inline void add(int x) {
    set<pair<int,int> > ::iterator q1;
    q1=s.lower_bound(make_pair(x+1,0));
    int l1=q1->first;
    int r1=q1->second;
    --q1;
    int l2=q1->first;
    int r2=q1->second;
    s.erase(s.find(make_pair(l1,r1)));
    s.erase(s.find(make_pair(l2,r2)));
    s.insert(make_pair(l2,r1));
    pair<int,int> res=get(1,sz,l2,r1,1);
    update(1,sz,l2,r1,1,res.first,res.second);
}

inline void del(int x) {
    set<pair<int,int> > ::iterator q1;
    q1=s.lower_bound(make_pair(x+1,0));
    --q1;
    int l1=q1->first;
    int r1=q1->second;
//    cout<<x<<" "<<l1<<" "<<r1<<'\n';
    s.erase(q1);
    s.insert(make_pair(l1,x));
    s.insert(make_pair(x+1,r1));
}

inline void solve() {
    sz=1;
    while (sz<n) sz+=sz;
    for (int i=1;i<=n;++i)
        t[sz+i-1]=make_pair(i,i);
    for (int i=sz-1;i>0;--i) {
        t[i].first=t[i+i].first;
        t[i].second=t[i+i+1].second;
    }
    for (int i=1;i<=sz+sz;++i)
        q[i]=make_pair(1e9,-1e9);
    for (int i=1;i<=n;++i)
        s.insert(make_pair(i,i));
    for (int i=1;i<=m;++i) {
        cin>>x;
        c[x]^=1;
        if (c[x]) add(x);
        else del(x);
    }
    for (int i=1;i<sz;++i)
        push(i);
    for (int i=1;i<=n;++i) {
        ans2[i].first=min(i,t[sz+i-1].first);
        ans2[i].second=max(i,t[sz+i-1].second);
    }
    while (qq--) {
        cin>>x;
        cout<<ans2[x].second-ans2[x].first+1<<'\n';
    }

}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m>>qq;
    bool t=false;
    for (int i=1;i<n;++i) {
        cin>>x>>y;
        if (x!=i || y!=i+1) t=true;
        v[x].push_back(make_pair(y,i));
        v[y].push_back(make_pair(x,i));
        f[i]=m+2;
        last[i]=m+1;
    }
    if (t==false) {
        solve();
        return 0;
    }
    for (int i=1;i<=m;++i) {
        cin>>x;
        c[x]^=1;
        if (c[x]) {
            f[x]=min(f[x],i);
        } else last[x]=i;
    }
    for (int i=1;i<n;++i) {
        if (c[i]) last[i]=m+1;
    }

    for (int i=1;i<=qq;++i) {
        cin>>x;
        ans=0;
        dfs(x,-1,0,1e9);
        cout<<ans<<'\n';
    }
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Incorrect 6 ms 5224 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 70 ms 12300 KB Output is correct
2 Correct 55 ms 12300 KB Output is correct
3 Correct 259 ms 19088 KB Output is correct
4 Correct 234 ms 19088 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19088 KB Output is correct
2 Correct 6 ms 19088 KB Output is correct
3 Correct 7 ms 19088 KB Output is correct
4 Correct 6 ms 19088 KB Output is correct
5 Correct 6 ms 19088 KB Output is correct
6 Correct 9 ms 19088 KB Output is correct
7 Correct 37 ms 19088 KB Output is correct
8 Correct 489 ms 22492 KB Output is correct
9 Correct 481 ms 25400 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 25424 KB Output is correct
2 Correct 287 ms 28084 KB Output is correct
3 Correct 251 ms 30556 KB Output is correct
4 Correct 272 ms 32788 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 32788 KB Output is correct
2 Incorrect 8 ms 32788 KB Output isn't correct
3 Halted 0 ms 0 KB -