Submission #986057

#	Time	Username	Problem	Language	Result	Execution time	Memory
986057		yeediot	Synchronization (JOI13_synchronization)	C++17	100 / 100	803 ms	35924 KiB

synchronization

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
#define why_TOI_is_so_de ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);setio();
const int mxn=1e5+5;
struct BIT{
    int bit[mxn];
    void init(){
        for(int i=0;i<mxn;i++){
            bit[i]=0;
        }
    }
    void modify(int p,int v){
        for(;p<mxn;p+=p&-p){
            bit[p]+=v;
        }
    }
    void modify(int l,int r,int v){
        modify(l,v);
        modify(r+1,-v);
    }
    int query(int p){
        int res=0;
        for(;p;p-=p&-p){
            res+=bit[p];
        }
        return res;
    }
    int query(int l,int r){
        return query(r)-query(l);
    }
}bt;
int n, m, q, timer=0, in[mxn], out[mxn], jump[20][mxn], dep[mxn], ans[mxn], last[mxn];
pair<int,int>edges[mxn];
vector<int>adj[mxn];
bool ex[mxn];
void dfs(int v,int pa){
    in[v]=++timer;
    jump[0][v]=pa;
    dep[v]=dep[pa]+1;
    for(auto u:adj[v]){
        if(u==pa)
            continue;
        dfs(u,v);
    }
    out[v]=timer;
}
int find(int x){
    for(int i=19;i>=0;i--){
        int y=jump[i][x];
        if(bt.query(in[y],in[x])==(1<<i)){
            x=y;
        }
    }
    return x;
}
signed main(){
    why_TOI_is_so_de;
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        cin>>edges[i].F>>edges[i].S;
        adj[edges[i].F].pb(edges[i].S);
        adj[edges[i].S].pb(edges[i].F);
    }
    for(int i=1;i<=n;i++){
        ans[i]=1;
    }
    dfs(1,1);
    bt.init();
    for(int i=1;i<n;i++){
        auto &[a,b]=edges[i];
        if(dep[a]<dep[b])swap(a,b);
    }
    for(int i=1;i<20;i++){
        for(int j=1;j<=n;j++){
            jump[i][j]=jump[i-1][jump[i-1][j]];
        }
    }
    for(int i=0;i<m;i++){
        int id;
        cin>>id;
        auto [v,u]=edges[id];
        int tv=find(v),tu=find(u);
        if(!ex[id]){
            int val=ans[tv]+ans[tu]-last[id];
            last[id]=0;
            bt.modify(in[v],out[v],1);
            ans[tu]=val;
        }
        else{
            last[id]=ans[tu];
            bt.modify(in[v],out[v],-1);
            tv=find(v),tu=find(u);
            ans[tv]=ans[tu]=last[id];
        }
        ex[id]=!ex[id];
    }
    while(q--){
        int x;
        cin>>x;
        cout<<ans[find(x)]<<'\n';
    }
    #ifdef local
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
}
/*
input:
 
*/















 

Compilation message (stderr)

synchronization.cpp: In function 'void setIO(std::string)':
synchronization.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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