Submission #153791

#	Time	Username	Problem	Language	Result	Execution time	Memory
153791		Mercenary	Synchronization (JOI13_synchronization)	C++14	100 / 100	271 ms	18808 KiB

synchronization

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;

const int maxn = 1e5 + 5;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;

int n , m , q;
int in[maxn] , out[maxn] ,id[maxn * 2];
int dp[maxn] , last[maxn];
int s[maxn * 8];
void build(int x , int l , int r){
    if(l == r){
        s[x] = out[id[l]];
        return;
    }
    int mid = l + r >> 1;
    build(x * 2 , l , mid);
    build(x * 2 + 1 , mid + 1 , r);
    s[x] = max(s[x * 2] , s[x * 2 + 1]);
}

void update(int x , int l , int r , int pos , int val){
    if(l == r){
        s[x] = val;
        return;
    }
    int mid = l + r >> 1;
    if(mid >= pos)update(x * 2 , l , mid , pos , val);
    else update(x * 2 + 1 , mid + 1 , r , pos , val);
    s[x] = max(s[x * 2] , s[x * 2 + 1]);
}

int query(int x , int l , int r , int pos , int val){
    if(l > pos || s[x] <= val)return 0;
    if(l == r)return l;
    int mid = l + r >> 1;
    int rig = query(x * 2 + 1 , mid + 1 , r , pos , val);
    if(rig != 0)return rig;
    return query(x * 2 , l , mid , pos , val);
}

ii e[maxn];
int state[maxn];
vector<int> adj[maxn];
void DFS(int u , int par){
    static int nTime = 0;
    in[u] = ++nTime;
    id[nTime] = u;
    for(int c : adj[u]){
        if(e[c].first + e[c].second - u != par){
            DFS(e[c].first + e[c].second - u , u);
        }
    }
    out[u] = ++nTime;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    if(fopen(taskname".INP","r")){
        freopen(taskname".INP", "r",stdin);
        freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> m >> q;
    for(int i = 1 ; i < n ; ++i){
        cin >> e[i].first >> e[i].second;
        adj[e[i].first].pb(i);
        adj[e[i].second].pb(i);
    }
    DFS(1 , 0);
    for(int i = 1 ; i < n ; ++i){
        if(in[e[i].first] > in[e[i].second])swap(e[i].first , e[i].second);
    }
    build(1 , 1 , n * 2);
    for(int i = 1 ; i <= n ; ++i)dp[i] = 1;
    while(m--){
        int i;cin >> i;
        int v = e[i].second;
        int u = id[query(1 , 1 , n * 2 , in[e[i].first] , in[e[i].first])];
        state[i] ^= 1;
        if(state[i]){
            dp[u] += dp[v] - last[v];
            update(1 ,1 , n * 2 , in[v] , in[v]);
        }else{
            dp[v] = last[v] = dp[u];
            update(1 ,1 , n * 2 , in[v] , out[v]);
        }
    }
    while(q--){
        int u;cin >> u;
//        cout << in[u] << " ";
//        cout << query(1 , 1 , n , in[u] , in[u]) << " ";
        cout << dp[id[query(1 , 1 , n * 2 , in[u] , in[u])]] << '\n';
    }
}

Compilation message (stderr)

synchronization.cpp: In function 'void build(int, int, int)':
synchronization.cpp:22:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
synchronization.cpp: In function 'void update(int, int, int, int, int)':
synchronization.cpp:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
synchronization.cpp: In function 'int query(int, int, int, int, int)':
synchronization.cpp:42:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP", "r",stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".OUT", "w",stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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