oj.uz

Submission #857208

# Submission time Handle Problem Language Result Execution time Memory
857208 2023-10-05T15:23:35 Z nnhzzz Synchronization (JOI13_synchronization) C++14
100 / 100
 635 ms 26452 KB 
// cre: Nguyen Ngoc Hung - Train VOI 2024 :>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <cmath>
#include <array>
#include <cassert>
#include <random>

using namespace std;

#define        __nnhzzz__  signed main()
#define          BIT(i,j)  ((i>>j)&1LL)
#define           MASK(i)  (1LL<<i)
#define            ALL(x)  (x).begin(),(x).end()
#define             SZ(x)  (int)(x).size()
#define                fi  first
#define                se  second
#define                ll  long long
#define                vi  vector<int>
#define               vvi  vector<vi>
#define               pii  pair<int,int>
#define              vpii  vector<pii>
#define REPDIS(i,be,en,j)  for(int i = (be); i<=(en); i+=j)
#define     REPD(i,be,en)  for(int i = (be); i>=(en); i--)
#define      REP(i,be,en)  for(int i = (be); i<=(en); i++)
//-------------------------------------------------------------//
const int oo = 1e9,LOG = 17,MAXN = 1e5+7,N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; }
template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; }

/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Nguyen Ngoc Hung - nnhzzz
    Training for VOI24 gold medal
----------------------------------------------------------------
*/

struct FENWICK_TREE{
    vi f;
    int n;

    void update(int id, int val){
        for(; id<=n; id+=id&-id){
            f[id] += val;
        }
    }

    int get(int id){
        int res = 0;
        for(; id>0; id-=id&-id){
            res += f[id];
        }
        return res;
    }

    FENWICK_TREE(int _ = 0):n(_){
        f.assign(n+1,0);
    }
}fen;

int tin[MAXN],tout[MAXN],f[MAXN][LOG],lst[MAXN],s[MAXN],ok[MAXN];
pii edge[MAXN];
vi adj[MAXN];
int timer = 0;

void dfs(int u, int par){
    REP(i,1,LOG-1) f[u][i] = f[f[u][i-1]][i-1];
    tin[u] = ++timer;
    for(const auto &v:adj[u]){
        if(v==par) continue;
        f[v][0] = u;
        dfs(v,u);
    }
    tout[u] = timer;
}

int find(int u){
    int lca = u,val = fen.get(tin[u]);
    REPD(i,LOG-1,0){
        if(f[lca][i]!=0 && fen.get(tin[f[lca][i]])==val) lca = f[lca][i];
    }
    return lca;
}

void solve(){
    int cur = 0,n,m,q; cin >> n >> m >> q;
    REP(i,1,n-1){
        auto &[u,v] = edge[i]; cin >> u >> v;
        cerr << u << " " << v << endl;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    REP(i,1,n) s[i] = 1;
    dfs(1,0);
    fen = FENWICK_TREE(n+1);
    REP(i,1,n){
        fen.update(tin[i],-1);
        fen.update(tout[i]+1,1);
    }
    while(m--){
        int pos; cin >> pos;
        auto [u,v] = edge[pos];
        if(f[u][0]==v) swap(u,v);
        if(ok[pos]==0){
            s[find(u)] += s[v]-lst[v];
            fen.update(tin[v],1);
            fen.update(tout[v]+1,-1);
        }else{
            s[v] = lst[v] = s[find(u)];
            fen.update(tin[v],-1);
            fen.update(tout[v]+1,1);
        }
        ok[pos] ^= 1;
    }
    while(q--){
        int pos; cin >> pos;
        cout << s[find(pos)] << "\n";
    }
}

__nnhzzz__{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define name "test"
    if(fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    #define name1 "disconnect"
    if(fopen(name1".in","r")){
        freopen(name1".in","r",stdin);
        freopen(name1".out","w",stdout);
    }

    int test = 1;

    while(test--){
      solve();
    }
    cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Compilation message

synchronization.cpp: In function 'void solve()':
synchronization.cpp:128:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  128 |         auto &[u,v] = edge[i]; cin >> u >> v;
      |               ^
synchronization.cpp:142:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  142 |         auto [u,v] = edge[pos];
      |              ^
synchronization.cpp:126:9: warning: unused variable 'cur' [-Wunused-variable]
  126 |     int cur = 0,n,m,q; cin >> n >> m >> q;
      |         ^~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:166:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:167:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:171:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |         freopen(name1".in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:172:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         freopen(name1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 6 ms 4752 KB Output is correct
7 Correct 52 ms 6140 KB Output is correct
8 Correct 52 ms 6072 KB Output is correct
9 Correct 52 ms 6048 KB Output is correct
10 Correct 614 ms 19216 KB Output is correct
11 Correct 592 ms 19140 KB Output is correct
12 Correct 607 ms 25456 KB Output is correct
13 Correct 485 ms 18736 KB Output is correct
14 Correct 510 ms 18496 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 22096 KB Output is correct
2 Correct 504 ms 22100 KB Output is correct
3 Correct 506 ms 24792 KB Output is correct
4 Correct 499 ms 24648 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 6 ms 4768 KB Output is correct
7 Correct 66 ms 6784 KB Output is correct
8 Correct 617 ms 26452 KB Output is correct
9 Correct 608 ms 26192 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 26196 KB Output is correct
2 Correct 537 ms 25944 KB Output is correct
3 Correct 541 ms 26200 KB Output is correct
4 Correct 567 ms 26040 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 6 ms 4748 KB Output is correct
6 Correct 55 ms 6036 KB Output is correct
7 Correct 588 ms 20032 KB Output is correct
8 Correct 622 ms 26284 KB Output is correct
9 Correct 502 ms 19916 KB Output is correct
10 Correct 530 ms 19996 KB Output is correct
11 Correct 520 ms 23152 KB Output is correct
12 Correct 523 ms 23236 KB Output is correct
13 Correct 541 ms 26152 KB Output is correct