Submission #70371

#	Time	Username	Problem	Language	Result	Execution time	Memory
70371		Benq	Synchronization (JOI13_synchronization)	C++14	100 / 100	2230 ms	140216 KiB

synchronization

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int N,M,Q, X[MX], Y[MX];
vi change[MX];

int numLE(vi& v, int x) { return distance(v.begin(),ub(all(v),x)); }

void merge(vi& a, vi& b) {
    if (sz(a) < sz(b)) swap(a,b);
    a.insert(a.end(),all(b));
}

void comb(map<int,vi>& a, map<int,vi>& b) {
    if (sz(a) < sz(b)) swap(a,b);
    for (auto& x: b) merge(a[x.f],x.s);
    b.clear();
}
    
template<int SZ> struct centroidDecomp {
    int sub[SZ], par[SZ];
    bool done[SZ];
    pi cen[SZ];
    vi fromCentroid[SZ]; // from (cen) to (vertex at time N)
    vi stor[SZ]; vector<vi> stor2[SZ]; // from (vertex at time 1) to cen
    vpi adj[SZ];
    
    // ACTUAL
    
    map<int,vi> fc[MX], tc[MX];
    
    void elimfc(map<int,vi>& m, int x) {
        for (int i = 0; i <= sz(change[x]); i += 2) {
            int l = (i > 0 ? change[x][i-1] : -MOD);
            int r = (i == sz(change[x]) ? MOD : change[x][i]-1);
            while (1) {
                auto it = m.ub(l);
                if (it != m.end() && it->f <= r) {
                    merge(m[l],it->s);
                    m.erase(it);
                } else break;
            }
        }
    }
    
    void elimtc(map<int,vi>& m, int x) {
        for (int i = 0; i <= sz(change[x]); i += 2) {
            int l = (i > 0 ? change[x][i-1]+1 : -MOD), r = (i == sz(change[x]) ? MOD : change[x][i]);
            while (1) {
                auto it = m.lb(l);
                if (it != m.end() && it->f < r) {
                    merge(m[r],it->s);
                    m.erase(it);
                } else break;
            }
        }
    }
    
    void gen(pi par, int no) {
        fc[no].clear(), tc[no].clear();
        fc[no][M].pb(no); tc[no][1].pb(no);
        
        for (auto i: adj[no]) if (!done[i.f] && i.f != par.f) {
            cen[i.f] = cen[no];
            gen({no,i.s},i.f);
            comb(fc[no],fc[i.f]); comb(tc[no],tc[i.f]);
        }
        
        elimfc(fc[no],par.s);
        elimtc(tc[no],par.s);
    }
    
    void doStuff(int x) {
        fromCentroid[x].pb(M); stor[x].pb(1);
        
        int co = 0;
        for (auto i: adj[x]) if (!done[i.f]) {
            cen[i.f] = {x,co};
            stor2[x].pb({});
            gen({x,i.s},i.f);
            for (auto a: fc[i.f]) for (auto b: a.s) {
                fromCentroid[b].pb(a.f);
                // cout << "AH " << x << " " << b << " " << a.f << "\n";
            }
            for (auto a: tc[i.f]) for (auto b: a.s) {
                stor[x].pb(a.f); 
                stor2[x][co].pb(a.f);
            }
            co ++;
        }
        /*cout << x << "\n";
        for (int i: stor[x]) cout << i << " ";
        exit(0);*/
        
        sort(all(stor[x])); F0R(i,co) sort(all(stor2[x][i]));
    }
        
    int query(int v) {
        int ret = 0;
        pi V; int ind; 
        for (V = {v,-1}, ind = sz(fromCentroid[v])-1; V.f; V = cen[V.f], ind --) {
            int d = fromCentroid[v][ind];
            // cout << "OOPS " << v << " " << V.f << " " << d << "\n";
            // cout << "OOPS " << d << "\n";
            
            ret += numLE(stor[V.f],d);
            if (V.s != -1) ret -= numLE(stor2[V.f][V.s],d);
        }
        return ret;
    }
    
    // centroid decomp
    
    void addEdge(int a, int b, int c) { adj[a].pb({b,c}), adj[b].pb({a,c}); }
    
    void dfs (int no) {
        sub[no] = 1;
        for (auto i: adj[no]) if (!done[i.f] && i.f != par[no]) {
            par[i.f] = no;
            dfs(i.f);
            sub[no] += sub[i.f];
        }
    }
    
    int getCentroid(int x) {
        par[x] = 0; dfs(x);
        int sz = sub[x];
        while (1) {
            pi mx = {0,0};
            for (auto i: adj[x]) if (!done[i.f] && i.f != par[x]) mx = max(mx,{sub[i.f],i.f});
            if (mx.f*2 > sz) x = mx.s;
            else return x;
        }
    }
    
    void solve (int x) {
        x = getCentroid(x); done[x] = 1;
        doStuff(x);
        for (auto i: adj[x]) if (!done[i.f]) solve(i.f);
    }
};

centroidDecomp<MX> cen;

void init() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M >> Q;
    FOR(i,1,N) {
        cin >> X[i] >> Y[i];
        cen.addEdge(X[i],Y[i],i);
    }
    FOR(i,1,M+1) {
        int D; cin >> D;
        change[D].pb(i);
    }
}

int main() {
    init();
    cen.solve(1);
    F0R(i,Q) {
        int C; cin >> C;
        cout << cen.query(C) << "\n";
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
* if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
*/

Compilation message (stderr)

synchronization.cpp: In instantiation of 'void centroidDecomp<SZ>::doStuff(int) [with int SZ = 100001]':
synchronization.cpp:182:16:   required from 'void centroidDecomp<SZ>::solve(int) [with int SZ = 100001]'
synchronization.cpp:204:16:   required from here
synchronization.cpp:129:45: warning: unused variable 'b' [-Wunused-variable]
             for (auto a: tc[i.f]) for (auto b: a.s) {
                                             ^

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