Submission #1177388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177388		vnedu	Synchronization (JOI13_synchronization)	C++20	60 / 100	229 ms	20804 KiB

synchronization

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 1e5 + 15;
const int M = 2e5 + 25;
const int Q = 1e5 + 15;

int numNode,numState,numQuery,query[Q],state[M];
vector<ii> adj[N];
ii edge[N];
namespace sub1
{
    bool check()
    {
        return (numQuery==1);
    }
    bool cmp(ii x, ii y)
    {
        return x.fi>y.fi;
    }
    int lst[N];
    vector<ii> t[N];
    int dfs(int u, int pa, int time)
    {
//        cout<<u<<' '<<pa<<' '<<time<<'\n';
        int ans=0;
        for (ii p : adj[u])
        {
            int v=p.fi,id=p.se;
            if (v==pa) continue;
            auto it=lower_bound(all(t[id]),make_pair(time,INT_MIN),cmp);
            int cm=INT_MIN;
            if (it!=t[id].end()) maximize(cm,(*it).fi);
            if (it!=t[id].begin())
            {
                --it;
                if (time>=(*it).se) maximize(cm,time);
            }
            if (cm!=INT_MIN) ans+=1+dfs(v,u,cm);
        }
        return ans;
    }
    void solve()
    {
        memset(lst,-1,sizeof(lst));
        for (int tri=1; tri<=numState; ++tri)
        {
            int x=state[tri];
            if (lst[x]==-1) lst[x]=tri;
            else
            {
                t[x].pb(make_pair(tri-1,lst[x]));
                lst[x]=-1;
            }
        }
        for (int i=1; i<numNode; ++i)
        {
            if (lst[i]!=-1) t[i].pb(make_pair(numState,lst[i]));
            reverse(all(t[i]));
        }
//        for (int i=1; i<numNode; ++i)
//        {
//            for (ii cm : t[i]) cout<<cm.fi<<' '<<cm.se<<'\n';
//            cout<<'\n';
//        }
        cout<<dfs(query[1],-1,numState)+1;
    }
}
namespace sub2
{
    bool check()
    {
        for (int i=1; i<numNode; ++i)
        {
            if (edge[i].fi!=i || edge[i].se!=i+1) return 0;
        }
        return 1;
    }
    vector<ii> time[N];
    int lst[N];
    ii laz[M<<2];
    void push(int id)
    {
        if (laz[id].fi!=-1)
        {
            laz[id<<1].fi=laz[id<<1|1].fi=laz[id].fi;
            laz[id<<1].se=laz[id<<1|1].se=0;
            laz[id].fi=-1;
        }
        if (laz[id].se)
        {
            laz[id<<1].se+=laz[id].se;
            laz[id<<1|1].se+=laz[id].se;
            laz[id].se=0;
        }
    }
    void add(int id, int l, int r, int u, int v, int val)
    {
        if (l>v||r<u) return;
        if (u<=l && r<=v)
        {
            laz[id].se+=val;
            return;
        }
        push(id);
        int mid((l+r)>>1);
        add(id<<1,l,mid,u,v,val);
        add(id<<1|1,mid+1,r,u,v,val);
    }
    void update(int id, int l, int r, int u, int v, int val)
    {
//        if (u==1 && v==5) cout<<l<<' '<<r<<'\n';
        if (l>v||r<u) return;
        if (u<=l && r<=v)
        {
//            if (u==1 && v==5) cout<<l<<' '<<r<<'\n';
            laz[id].fi=val; laz[id].se=0;
            return;
        }
        push(id);
        int mid((l+r)>>1);
        update(id<<1,l,mid,u,v,val);
        update(id<<1|1,mid+1,r,u,v,val);
    }
    int get(int x)
    {
        int id=1,l=1,r=numState,mid;
        while (l!=r)
        {
            mid=(l+r)>>1;
            push(id);
            if (x<=mid) r=mid,id=(id<<1);
            else l=mid+1,id=(id<<1|1);
        }
//        cout<<laz[id].fi<<' '<<laz[id].se<<' ';
        return laz[id].fi+laz[id].se;
    }
    int ans[N];
    void solve()
    {
        memset(lst,-1,sizeof(lst));
        for (int tri=1; tri<=numState; ++tri)
        {
            int x=state[tri];
            if (lst[x]==-1) lst[x]=tri;
            else
            {
                time[x].pb(make_pair(lst[x],tri-1));
                lst[x]=-1;
            }
        }
        for (int i=1; i<numNode; ++i)
        {
            if (lst[i]!=-1) time[i].pb(make_pair(lst[i],numState));
        }
        for (int id=1; id<numNode; ++id)
        {
            for (ii cm : time[id]) add(1,1,numState,cm.fi,cm.se,1);
            int sz=(int)time[id].size();
            for (int i=0; i<sz; ++i)
            {
                int x=get(time[id][i].se);
                int l=time[id][i].se+1,r=(i==sz-1?numState:time[id][i+1].fi-1);
                if (l<=r) update(1,1,numState,l,r,x);
            }
            int l=1,r=(sz==0?numState:time[id][0].fi-1);
//            cout<<"DSAD\n";
            if (l<=r) update(1,1,numState,l,r,0);
//            if (id==3) cout<<l<<' '<<r<<'\n';
//            if (id==3)
//            {
//                for (int i=1; i<=numState; ++i) cout<<get(i)<<'\n';
//                cout<<'\n';
//            }
            ans[id+1]+=get(numState);
        }
//        for (int id=1; id<numNode; ++id)
//        {
//            for (ii cm : time[id]) cout<<cm.fi<<' '<<cm.se<<'\n';
//            cout<<'\n';
//        }
        update(1,1,numState,1,numState,0);
//        for (int i=1; i<=numState; ++i) cout<<get(i)<<' ';
//        cout<<'\n';
//        return;
        for (int id=numNode; id>=2; --id)
        {
            for (ii cm : time[id-1]) add(1,1,numState,cm.fi,cm.se,1);
            int sz=(int)time[id-1].size();
            for (int i=0; i<sz; ++i)
            {
                int x=get(time[id-1][i].se);
                int l=time[id-1][i].se+1,r=(i==sz-1?numState:time[id-1][i+1].fi-1);
                if (l<=r) update(1,1,numState,l,r,x);
            }
            int l=1,r=(sz==0?numState:time[id-1][0].fi-1);
            if (l<=r) update(1,1,numState,l,r,0);
            ans[id-1]+=get(numState);
        }
        for (int i=1; i<=numNode; ++i)
        {
            ++ans[i];
        }
        for (int tri=1; tri<=numQuery; ++tri)
        {
            cout<<ans[query[tri]]<<'\n';
        }
    }
}
void solve()
{
    cin>>numNode>>numState>>numQuery;
    for (int i=1; i<numNode; ++i)
    {
        int u,v; cin>>u>>v;
        edge[i]={u,v};
        adj[u].pb({v,i});
        adj[v].pb({u,i});
    }
    for (int i=1; i<=numState; ++i) cin>>state[i];
    for (int i=1; i<=numQuery; ++i) cin>>query[i];
    if (sub1::check()) return void(sub1::solve());
    if (sub2::check()) return void(sub2::solve());
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

//    #define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
//    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}

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