oj.uz

Submission #153791

# Submission time Handle Problem Language Result Execution time Memory
153791 2019-09-16T10:14:26 Z Mercenary Synchronization (JOI13_synchronization) C++14
100 / 100
 271 ms 18808 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 7 ms 2808 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 6 ms 2812 KB Output is correct
7 Correct 21 ms 3832 KB Output is correct
8 Correct 19 ms 3832 KB Output is correct
9 Correct 19 ms 3832 KB Output is correct
10 Correct 216 ms 13816 KB Output is correct
11 Correct 222 ms 13848 KB Output is correct
12 Correct 187 ms 18168 KB Output is correct
13 Correct 149 ms 13764 KB Output is correct
14 Correct 171 ms 12868 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 13432 KB Output is correct
2 Correct 115 ms 15416 KB Output is correct
3 Correct 90 ms 17144 KB Output is correct
4 Correct 93 ms 17144 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2684 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2680 KB Output is correct
6 Correct 3 ms 2808 KB Output is correct
7 Correct 21 ms 4088 KB Output is correct
8 Correct 255 ms 15992 KB Output is correct
9 Correct 207 ms 15912 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 15864 KB Output is correct
2 Correct 129 ms 15984 KB Output is correct
3 Correct 124 ms 15992 KB Output is correct
4 Correct 127 ms 15964 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2684 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 22 ms 3960 KB Output is correct
7 Correct 271 ms 14600 KB Output is correct
8 Correct 202 ms 18808 KB Output is correct
9 Correct 220 ms 14852 KB Output is correct
10 Correct 201 ms 14216 KB Output is correct
11 Correct 148 ms 16632 KB Output is correct
12 Correct 151 ms 16744 KB Output is correct
13 Correct 131 ms 18256 KB Output is correct