Submission #238604

#	Time	Username	Problem	Language	Result	Execution time	Memory
238604		LightYear	Synchronization (JOI13_synchronization)	C++17	0 / 100	2430 ms	33440 KiB

synchronization

#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;

    auto add = [&](int l, int r, ll x) {
        tree.update(l, x), tree.update(r + 1, -x);
        tree2.update(l, -x*(l - 1)), tree2.update(r + 1, x*r);
    };

    auto val = [&](ll l) {
        return tree.sum(l) * l + tree2.sum(l);
    };

    auto rval = [&](ll l, ll r) {
        return val(r) - val(l - 1);
    };

    for(int i = 1; i <= n; i++)   add(st[i], st[i], 1), add(en[i], en[i], -1);
    auto findRep = [&](int u) {
        int hi = n, lo = 0, v, mid;

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

        v = get(u, lo);
        return v;
    };

    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];
            bef[v] = res[v];
            add(st[v] - 1, st[v] - 1, -1), add(en[v], en[v], 1);
            deb(cur, res[cur], u, v, bef[v], findRep(v), rval(st[v], st[v]));
        }
        else {
            res[v] = res[findRep(u)];
            add(st[v] - 1, st[v] - 1, 1), add(en[v], en[v], -1);
        }
        state[ind] = !state[ind];
    }

    int hi, lo, mid;
    while(q--) {
        cin >> u;
        v = findRep(u);
        cout << res[v] << "\n";
    }

    for(int i = 0; i <= 2*n + 1; i++)   cerr << rval(i, i) << " ";
    cerr << "\n";

    deb(findRep(4), tree.sum(st[2], st[4]));
}

Compilation message (stderr)

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:205:77: warning: statement has no effect [-Wunused-value]
             deb(cur, res[cur], u, v, bef[v], findRep(v), rval(st[v], st[v]));
                                                                             ^
synchronization.cpp:224:44: warning: statement has no effect [-Wunused-value]
     deb(findRep(4), tree.sum(st[2], st[4]));
                                            ^
synchronization.cpp:214:9: warning: unused variable 'hi' [-Wunused-variable]
     int hi, lo, mid;
         ^~
synchronization.cpp:214:13: warning: unused variable 'lo' [-Wunused-variable]
     int hi, lo, mid;
             ^~
synchronization.cpp:214:17: warning: unused variable 'mid' [-Wunused-variable]
     int hi, lo, mid;
                 ^~~
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){
     ^~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40