oj.uz

Submission #632032

# Submission time Handle Problem Language Result Execution time Memory
632032 2022-08-19T10:30:21 Z Soul234 Synchronization (JOI13_synchronization) C++14
100 / 100
 274 ms 25408 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

tcT> bool ckmin(T&a, const T&b) {
    return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a=b,1 : 0; }

const int MOD = 1e9 + 7;

struct BIT {
    int N;
    vi bit;
    void init(int _N) {
        N = _N;
        bit.assign(N + 7, 0);
    }
    void updInc(int p, int val) {
        for(; p<=N; p += p&-p) bit[p] += val;
    }
    int query(int p) {
        int res = 0;
        for(; p>0; p -= p&-p) res += bit[p];
        return res;
    }
} fen;

const int MX = 1e5+5, LG = 18;
int N, M, Q, tt, tin[MX], tout[MX], par[MX][LG], isact[MX], cnt[MX], lst[MX];
vi adj[MX];
pi eds[MX];

void dfs(int u, int p) {
    tin[u] = ++tt;
    cnt[u] = 1;
    each(v, adj[u]) if(v != p) {
        par[v][0] = u;
        dfs(v, u);
    }
    tout[u] = tt;
}

int get_anc(int u) {
    int res = u;
    R0F(i, LG) if(fen.query(tin[par[res][i]]) == fen.query(tin[u]))
        res = par[res][i];
    return res;
}

void solve() {
    cin >> N >> M >> Q;
    fen.init(N+5);
    F0R(i, N-1) {
        int u,v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
        eds[i+1] = {u, v};
    }
    par[1][0] = 1;
    dfs(1, -1);
    FOR(j,1,LG) FOR(i,1,N+1) par[i][j] = par[par[i][j-1]][j-1];
    FOR(i,2,N+1) {
        fen.updInc(tin[i], 1);
        fen.updInc(tout[i]+1, -1);
    }
    F0R(i, M) {
        int ind;
        cin >> ind;
        int u = eds[ind].first, v = eds[ind].second;
        if(par[u][0] == v) swap(u, v);
        if(isact[v]) {
            int rt = get_anc(u);
            cnt[v] = lst[v] = cnt[rt];
            fen.updInc(tin[v], 1);
            fen.updInc(tout[v]+1, -1);
        }
        else {
            int rt = get_anc(u);
            cnt[rt] = cnt[rt] + cnt[v] - lst[v];
            fen.updInc(tin[v], -1);
            fen.updInc(tout[v]+1, 1);
        }
        isact[v] ^= 1;
    }
    while(Q-- > 0) {
        int v; cin >> v;
        v = get_anc(v);
        cout << cnt[v] << nl;
    }
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2792 KB Output is correct
7 Correct 13 ms 4180 KB Output is correct
8 Correct 13 ms 4240 KB Output is correct
9 Correct 13 ms 4248 KB Output is correct
10 Correct 194 ms 18368 KB Output is correct
11 Correct 178 ms 18364 KB Output is correct
12 Correct 203 ms 24448 KB Output is correct
13 Correct 90 ms 18200 KB Output is correct
14 Correct 122 ms 17340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 20972 KB Output is correct
2 Correct 91 ms 20728 KB Output is correct
3 Correct 93 ms 23524 KB Output is correct
4 Correct 91 ms 23520 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 21 ms 4820 KB Output is correct
8 Correct 274 ms 25408 KB Output is correct
9 Correct 261 ms 25288 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 25276 KB Output is correct
2 Correct 147 ms 24600 KB Output is correct
3 Correct 150 ms 24764 KB Output is correct
4 Correct 144 ms 24768 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2828 KB Output is correct
6 Correct 20 ms 4288 KB Output is correct
7 Correct 258 ms 19160 KB Output is correct
8 Correct 247 ms 25308 KB Output is correct
9 Correct 134 ms 19320 KB Output is correct
10 Correct 162 ms 18816 KB Output is correct
11 Correct 121 ms 22132 KB Output is correct
12 Correct 120 ms 22292 KB Output is correct
13 Correct 182 ms 24748 KB Output is correct