Submission #52195

#	Time	Username	Problem	Language	Result	Execution time	Memory
52195		Smelskiy	Synchronization (JOI13_synchronization)	C++14	20 / 100	263 ms	32616 KiB

synchronization

#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;
int sz;
pair<int,int> q[500005];
pair<int,int> ans2[500005];

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);
        return;
    }
    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);
}

inline void add(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;
    s.erase(q1);
    q1=s.lower_bound(make_pair(x+1,0));
    --q1;
    int l2=q1->first;
    int r2=q1->second;
    s.erase(q1);
    s.insert(make_pair(l2,r1));
//    cout<<">"<<l2<<" "<<r1<<'\n';
    update(1,sz,l2,r1,1,l2,r1);
}

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

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

}

inline void solve() {
    sz=1;
    while (sz<n) sz+=sz;
    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,q[sz+i-1].first);
        ans2[i].second=max(i,q[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 (stderr)

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) {
                  ~^~~~~~~~~~~~
synchronization.cpp: In function 'void add(int)':
synchronization.cpp:49:9: warning: unused variable 'l1' [-Wunused-variable]
     int l1=q1->first;
         ^~
synchronization.cpp:55:9: warning: unused variable 'r2' [-Wunused-variable]
     int r2=q1->second;
         ^~

• Subtask 1: 0 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40