oj.uz

Submission #153788

# Submission time Handle Problem Language Result Execution time Memory
153788 2019-09-16T10:07:52 Z Mercenary Synchronization (JOI13_synchronization) C++14
30 / 100
 211 ms 17784 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];
int dp[maxn] , last[maxn];
int s[maxn * 4];
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 -1;
    if(l == r)return l;
    int mid = l + r >> 1;
    int rig = query(x * 2 + 1 , mid + 1 , r , pos , val);
    if(rig != -1)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);
    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 , in[e[i].first] , in[e[i].first])];
//        cout << query(1 , 1 , n , in[e[i].first] , in[e[i].first]) << " ";
//        cout << " " << query(1 , 1 , n , in[e[i].first] , in[e[i].first]) << " " << u << endl;
        state[i] ^= 1;
        if(state[i]){
            dp[u] += dp[v] - last[v];
            update(1 ,1 , n , in[v] , in[v]);
//            cout << in[v] << " " << in[v] << endl;
        }else{
            dp[v] = last[v] = dp[u];
            update(1 ,1 , n , in[v] , out[v]);
//            cout << in[v] << " " << out[v] << endl;
        }
    }
    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 , 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2684 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Incorrect 5 ms 2680 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 14328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 5 ms 2680 KB Output is correct
6 Correct 8 ms 2808 KB Output is correct
7 Correct 19 ms 4216 KB Output is correct
8 Correct 210 ms 17784 KB Output is correct
9 Correct 203 ms 17784 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 17776 KB Output is correct
2 Correct 128 ms 17268 KB Output is correct
3 Correct 124 ms 17276 KB Output is correct
4 Correct 124 ms 17216 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Incorrect 5 ms 2680 KB Output isn't correct
3 Halted 0 ms 0 KB -