Submission #238616

# Submission time Handle Problem Language Result Execution time Memory
238616 2020-06-12T07:57:13 Z LightYear Synchronization (JOI13_synchronization) C++17
100 / 100
1304 ms 33080 KB
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
const ll MOD = 998244353;
const ll INF = 1e18;
using namespace std;

vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifdef XOX
#define deb(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define deb(...) 42
#endif

template<typename T>
struct FenwickTree{
    vector<T> bit;
    int n;
 
    FenwickTree(int num) : n(num), bit(num, (T)0){
    }
 
    T sum(int r){
        T ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }
 
    T sum(int l, int r){
        return sum(r) - sum(l - 1);
    }
 
    void update(int idx, T delta){
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
 
    int lower_bound(T val){
        int cur = 20, pos = 0;
        T sum = 0;
        while(cur >= 0){
            if((pos + (1 << cur)) < n and (sum + bit[pos + (1 << cur)]) < val)    sum += bit[pos + (1 << cur)], pos += (1 << cur);
            cur--;
        }
        return pos + 1;
    }
 
    int upper_bound(T val){
        return lower_bound(val + ((T)1));
    }
};

int up[300000][21];
int depth[3000000];
vector<vector<int>> edges;
int l = 20;
void dfs(int u, int par = -1){
    if(par == -1){
        depth[u] = 0;
        up[u][0] = u;
    }
    else{
        depth[u] = depth[par] + 1;
        up[u][0] = par;
    }

    for(int i = 1; i < l; i++){
        up[u][i] = up[up[u][i-1]][i-1];
    }

    for(auto v : edges[u]){
        if(v != par){
            dfs(v, u);
        }
    }
}

int lca(int u, int v){
    if(depth[u] < depth[v])	swap(u, v);
    int dist = depth[u] - depth[v];
    for(int i = 0; i < l; i++)	if(dist&(1 << i))	u = up[u][i];
    if(u == v)	return u;

    for(int i = l-1; i >= 0; i--){
        if(up[u][i] != up[v][i])	u = up[u][i], v = up[v][i];
    }

    return up[u][0];
}

int dist(int u, int v){
    int w = lca(u, v);
    return depth[u] + depth[v] - (2 * depth[w]);
}

int get(int u, int len){
    for(int i = l - 1; i >= 0; i--)   if(len&(1 << i)) u = up[u][i];
    return u;
}

vector<int> euler;
int st[400000], en[400000];
ll res[400000];

void dfs2(int u, int par = -1){
    st[u] = euler.size();
    euler.push_back(u);
    for(auto v : edges[u]) {
        if(v != par)    dfs2(v, u), euler.push_back(u);
    }
    en[u] = euler.size() - 1;
}
ll bef[500000]; 

main(){    
    #ifdef XOX
        freopen("D:\\V S Code\\cpp\\competitiveProgramming\\Input.txt", "r", stdin);
        freopen("D:\\V S Code\\cpp\\competitiveProgramming\\OPT.txt", "w", stdout);
    #endif

    ios::sync_with_stdio(!cin.tie(NULL));
    
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int>> edge;
    edges.resize(n + 10);

    int u, v;
    for(int i = 1; i < n; i++) {
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
        edge.push_back({u, v});
    }

    dfs(1), dfs2(1);

    FenwickTree<ll> tree(2*n + 10), tree2(2*n + 10);
    memset(bef, 0, sizeof(bef));
    bool state[400000];
    memset(state, false, sizeof(state));
    int ind, cur;
    for(int i = 1; i <= n; i++) res[i] = 1;

    for(int i = 1; i <= n; i++) tree.update(st[i], 1), tree.update(en[i], -1);

    auto findRep = [&] (int u) {
        int hi = n, lo = 0, mid;
        int v;

        while(hi > lo) {
            mid = (hi + lo + 1) /2;
            v = get(u, mid);
            if(tree.sum(st[v], st[u] - 1))  hi = mid - 1;
            else    lo = mid;
        }

        return get(u, lo);
    };

    while(m--) {
        cin >> ind;
        ind--;
        if(depth[edge[ind].first] > depth[edge[ind].second])    swap(edge[ind].first, edge[ind].second);
        u = edge[ind].first, v = edge[ind].second;
        if(!state[ind]) {
            cur = findRep(u);
            res[cur] = res[cur] + res[v] - bef[v];
            tree.update(st[v] - 1, -1), tree.update(en[v], 1);
            deb(cur, st[v] - 1, en[v], v, u, res[cur]);
        }
        else {
            res[v] = res[findRep(v)];
            bef[v] = res[findRep(v)];
            tree.update(st[v] - 1, 1), tree.update(en[v], -1);
        }
        state[ind] = !state[ind];
    }

    while(q--) {
        cin >> u;
        cout << res[findRep(u)] << "\n";
    }

    deb(res[findRep(4)]);
}

Compilation message

synchronization.cpp:135:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){    
      ^
synchronization.cpp: In function 'int main()':
synchronization.cpp:190:55: warning: statement has no effect [-Wunused-value]
             deb(cur, st[v] - 1, en[v], v, u, res[cur]);
                                                       ^
synchronization.cpp:205:25: warning: statement has no effect [-Wunused-value]
     deb(res[findRep(4)]);
                         ^
synchronization.cpp: In instantiation of 'FenwickTree<T>::FenwickTree(int) [with T = long long int]':
synchronization.cpp:158:34:   required from here
synchronization.cpp:37:9: warning: 'FenwickTree<long long int>::n' will be initialized after [-Wreorder]
     int n;
         ^
synchronization.cpp:36:15: warning:   'std::vector<long long int, std::allocator<long long int> > FenwickTree<long long int>::bit' [-Wreorder]
     vector<T> bit;
               ^~~
synchronization.cpp:39:5: warning:   when initialized here [-Wreorder]
     FenwickTree(int num) : n(num), bit(num, (T)0){
     ^~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 7 ms 4608 KB Output is correct
2 Correct 7 ms 4608 KB Output is correct
3 Correct 7 ms 4608 KB Output is correct
4 Correct 7 ms 4608 KB Output is correct
5 Correct 7 ms 4736 KB Output is correct
6 Correct 11 ms 4864 KB Output is correct
7 Correct 38 ms 7040 KB Output is correct
8 Correct 38 ms 7040 KB Output is correct
9 Correct 38 ms 7040 KB Output is correct
10 Correct 552 ms 27752 KB Output is correct
11 Correct 524 ms 27628 KB Output is correct
12 Correct 1141 ms 32364 KB Output is correct
13 Correct 350 ms 27496 KB Output is correct
14 Correct 264 ms 26980 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 288 ms 27756 KB Output is correct
2 Correct 281 ms 29420 KB Output is correct
3 Correct 288 ms 31728 KB Output is correct
4 Correct 271 ms 31596 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 7 ms 4736 KB Output is correct
2 Correct 7 ms 4736 KB Output is correct
3 Correct 7 ms 4736 KB Output is correct
4 Correct 7 ms 4736 KB Output is correct
5 Correct 7 ms 4736 KB Output is correct
6 Correct 11 ms 4992 KB Output is correct
7 Correct 57 ms 7552 KB Output is correct
8 Correct 1284 ms 33004 KB Output is correct
9 Correct 1301 ms 32940 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1287 ms 30060 KB Output is correct
2 Correct 455 ms 32680 KB Output is correct
3 Correct 456 ms 32744 KB Output is correct
4 Correct 447 ms 32748 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 7 ms 4608 KB Output is correct
2 Correct 6 ms 4608 KB Output is correct
3 Correct 7 ms 4736 KB Output is correct
4 Correct 7 ms 4736 KB Output is correct
5 Correct 10 ms 4864 KB Output is correct
6 Correct 48 ms 7168 KB Output is correct
7 Correct 670 ms 28600 KB Output is correct
8 Correct 1304 ms 33080 KB Output is correct
9 Correct 471 ms 28584 KB Output is correct
10 Correct 400 ms 28268 KB Output is correct
11 Correct 433 ms 30980 KB Output is correct
12 Correct 408 ms 30956 KB Output is correct
13 Correct 463 ms 32880 KB Output is correct