Submission #337954

#	Time	Username	Problem	Language	Result	Execution time	Memory
337954		gmyu	Synchronization (JOI13_synchronization)	C++14	100 / 100	2756 ms	32484 KiB

synchronization

/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/JOI13_synchronization
Solution: https://bits-and-bytes.me/2020/01/05/JOI-2013-Synchronisation/
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define fst first
#define snd second
#define pb  push_back
#define sz(x) (int)(x).size()
#define trav(u, adj_v) for (auto& u: adj_v)

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 100007
#define MAXE 100007


/// code from USACO examples
void setIO(string name) {
    ios_base::sync_with_stdio(0); cin.tie(0);
}
bool debug = false, submit = true;

int N, M, Q;
vii edge;
vi active;
int dp[MAXV], dp0[MAXV];

/** lazy segment tree
 * Description: 1D range increment and sum query.
 * Source: USACO Counting Haybales
 * Verification: SPOJ Horrible
 */
#define MAXSEGSZ1E5   131072    // 2^17 for 1e5,
#define MAXSEGSZ2E5   262144    // 2^18 for 2e5,
#define MAXSEGSZ5E5   524288    // 2^19 for 5e5,

template<class T, int SZ> struct LazySeg {
	//static_assert(pct(SZ) == 1);
	/// SZ must be power of 2
	const T ID = 0;
	T comb(T a, T b) { return (a + b); }    /// this depends on operation you want
	T seg[2*SZ];
	LazySeg() { for(int i=0; i<2*SZ; i++) seg[i] = ID; }
	void initTree(int lo, int hi, int ind=1, int L=0, int R=SZ-1) {
		if (lo > R || L > hi) return;    /// this depends on operation you want
        if(L==R) { seg[ind] = 1; return; }
		int M = (L+R)/2;
		initTree(lo,hi,2*ind,L,M); initTree(lo,hi,2*ind+1,M+1,R);
		seg[ind] = seg[2*ind] + seg[2*ind+1];
	}
	void updNode(int vtx,T val,int ind=1,int L=0, int R=SZ-1) {   /// counting 0 .. SZ-1
		if(L == R) {seg[ind] = val; return; }
		int M = (L+R)/2;
		(vtx <= M) ? updNode(vtx,val,2*ind,L,M) : updNode(vtx,val,2*ind+1,M+1,R);
		seg[ind] = seg[2*ind] + seg[2*ind+1];
	}
	T query(int lo, int hi, int ind=1, int L=0, int R=SZ-1) {
		if (lo > R || L > hi) return 0;    /// this depends on operation you want
		if (lo <= L && R <= hi) return seg[ind];
		int M = (L+R)/2;
		return query(lo,hi,2*ind,L,M) + query(lo,hi,2*ind+1,M+1,R);
	}
};

/**
 * Description: Heavy-Light Decomposition, add val to verts
 	* and query sum in path/subtree.
 * Time: any tree path is split into $O(\log N)$ parts
 * Source: http://codeforces.com/blog/entry/22072, https://codeforces.com/blog/entry/53170
 * Verification: *
 */
 #define MAXLCALOG 20
template<int SZ> struct HLD {
    int edgeOffset = 0;
	int N; vi adj[SZ];
	int par[SZ], root[SZ], depth[SZ], sz[SZ], ti;
	int pos[SZ]; // pos is bascially its Euler ID, and pos+sz-1 is the end of Euler range
	vi rpos; // root positions, not used, but could be useful
    LazySeg<ll,SZ> tree; // segtree for sum
    int anc[MAXV][MAXLCALOG];

	void ae(int x, int y) { adj[x].pb(y), adj[y].pb(x); }
	void dfsSz(int x) {
		sz[x] = 1;
		trav(y,adj[x]) {
			par[y] = x; depth[y] = depth[x]+1;
			adj[y].erase(find(adj[y].begin(), adj[y].end(), x)); // remove parent from adj list
			dfsSz(y); sz[x] += sz[y];
			if (sz[y] > sz[adj[x][0]]) swap(y,adj[x][0]);
		}
	}
	void dfsHld(int x) {
		pos[x] = ti++; rpos.pb(x);  // it is travel is Euler walk, and each heavy path is together
		trav(y,adj[x]) {
			root[y] = (y == adj[x][0] ? root[x] : y);
			dfsHld(y); }
	}
	void prepLCA(int r) {
        for(int i = r; i <= N; i++) anc[i][0] = par[i];
        for(int j = 1; j < MAXLCALOG; j++)
            for(int i = r; i <= N; i++)
                anc[i][j] = anc[anc[i][j-1]][j-1];
    }
	void init(int _N, int R = 1) {
	    N = _N;
		par[R] = depth[R] = ti = 0; dfsSz(R);
		root[R] = R; dfsHld(R);
		prepLCA(R);
		tree.initTree(0, N-1);
	}
	int lca(int x, int y) {
		for (; root[x] != root[y]; y = par[root[y]])
			if (depth[root[x]] > depth[root[y]]) swap(x,y);
		return depth[x] < depth[y] ? x : y;
	}
	int findAnc(int x) {
	    int curr = x;
	    for(int k = MAXLCALOG - 1; k>=0; k--) {
            int p = anc[curr][k];
            if(p==0) continue;
            if(queryPath(curr, p) - queryPath(p, p) > 0) continue; /// the path has a broken line
            curr = p;
        }
        return curr;
	}
	void updTreeNode(int x, int val) {
        tree.updNode(pos[x], val);
	}
	// int dist(int x, int y) { // # edges on path
	// 	return depth[x]+depth[y]-2*depth[lca(x,y)]; }
	void modifyPath(int x, int y, int v) {
	    for (; root[x] != root[y]; y = par[root[y]]) {
			if (depth[root[x]] > depth[root[y]]) swap(x,y);
			tree.upd(pos[root[y]],pos[y],v);
        }
		if (depth[x] > depth[y]) swap(x,y);
		tree.upd(pos[x]+edgeOffset,pos[y],v);
    }
	ll queryPath(int x, int y) {    /// query operation needs to be updated
		ll res = 0;
		for (; root[x] != root[y]; y = par[root[y]]) {
			if (depth[root[x]] > depth[root[y]]) swap(x,y);
			res += tree.query(pos[root[y]],pos[y]);
        }
		if (depth[x] > depth[y]) swap(x,y);
		res += tree.query(pos[x]+edgeOffset,pos[y]);
		return res;
    }
	void modifySubtree(int x, int v) {
		tree.upd(pos[x]+edgeOffset,pos[x]+sz[x]-1,v); }
};

HLD<MAXSEGSZ1E5> myHld;

int main() {
    debug = false; submit = false;
    if(submit) setIO("testName");

    int i, j, k;
    int ans = 0;

    cin >> N >> M >> Q;
    for(i=1; i<=N-1; i++) {
        int a, b; cin >> a >> b;
        edge.pb(mp(a, b)); active.pb(0);
        myHld.ae(a, b);
    }

    myHld.init(N, 1);

    for(i=1; i<=N; i++) { dp[i] = 1; dp0[i] = 0; }

    for(i=0; i<M;i++) {
        int x; cin >> x; x--;
        int a = edge[x].fst, b = edge[x].snd;
        if(myHld.depth[a] > myHld.depth[b]) swap(a, b);
        int pa = myHld.findAnc(a);

        if(active[x] == 0) { // now connect
            dp[a] = dp[pa];
            dp[a] = dp[a] + dp[b] - dp0[b];
            dp[pa] = dp[a];
            myHld.updTreeNode(b, 0);
            active[x] = 1;
            if(debug) cout << "connect " << a << " " << b << " top at " << myHld.findAnc(b) << endl;
        } else {    // need to disconnect
            dp0[b] = dp[pa];
            dp[b] = dp[pa]; dp[a] = dp[pa];
            myHld.updTreeNode(b, 1);
            active[x] = 0;
            if(debug) cout << "disconnect " << a << " " << b << " top at " << myHld.findAnc(b) << endl;
        }
    }

    for(i=0; i < Q; i++){
        int a; cin >> a;
        int pa = myHld.findAnc(a);
        if(debug) cout << " anc is " << pa << endl;
        cout << dp[pa] << endl;
    }

}

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:182:12: warning: unused variable 'j' [-Wunused-variable]
  182 |     int i, j, k;
      |            ^
synchronization.cpp:182:15: warning: unused variable 'k' [-Wunused-variable]
  182 |     int i, j, k;
      |               ^
synchronization.cpp:183:9: warning: unused variable 'ans' [-Wunused-variable]
  183 |     int ans = 0;
      |         ^~~

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