oj.uz

Submission #986066

# Submission time Handle Problem Language Result Execution time Memory
986066 2024-05-19T17:19:16 Z yeediot Synchronization (JOI13_synchronization) C++17
100 / 100
 696 ms 35468 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23128 KB Output is correct
2 Correct 3 ms 23132 KB Output is correct
3 Correct 3 ms 23132 KB Output is correct
4 Correct 3 ms 23132 KB Output is correct
5 Correct 3 ms 23132 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct
7 Correct 26 ms 23644 KB Output is correct
8 Correct 26 ms 23644 KB Output is correct
9 Correct 26 ms 23640 KB Output is correct
10 Correct 647 ms 30528 KB Output is correct
11 Correct 696 ms 30812 KB Output is correct
12 Correct 530 ms 34672 KB Output is correct
13 Correct 386 ms 30404 KB Output is correct
14 Correct 344 ms 30288 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 32460 KB Output is correct
2 Correct 140 ms 32208 KB Output is correct
3 Correct 128 ms 34144 KB Output is correct
4 Correct 137 ms 34148 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23128 KB Output is correct
2 Correct 3 ms 23132 KB Output is correct
3 Correct 3 ms 23084 KB Output is correct
4 Correct 3 ms 23132 KB Output is correct
5 Correct 3 ms 23128 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct
7 Correct 28 ms 24152 KB Output is correct
8 Correct 616 ms 35468 KB Output is correct
9 Correct 622 ms 35348 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 35412 KB Output is correct
2 Correct 171 ms 35212 KB Output is correct
3 Correct 170 ms 35260 KB Output is correct
4 Correct 171 ms 35228 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23132 KB Output is correct
2 Correct 3 ms 23132 KB Output is correct
3 Correct 4 ms 23132 KB Output is correct
4 Correct 3 ms 23132 KB Output is correct
5 Correct 5 ms 23132 KB Output is correct
6 Correct 29 ms 23900 KB Output is correct
7 Correct 696 ms 31480 KB Output is correct
8 Correct 593 ms 35412 KB Output is correct
9 Correct 403 ms 31432 KB Output is correct
10 Correct 391 ms 31268 KB Output is correct
11 Correct 174 ms 33488 KB Output is correct
12 Correct 180 ms 33432 KB Output is correct
13 Correct 176 ms 35144 KB Output is correct