oj.uz

Submission #337954

# Submission time Handle Problem Language Result Execution time Memory
337954 2020-12-22T07:18:22 Z gmyu Synchronization (JOI13_synchronization) C++14
100 / 100
 2756 ms 32484 KB 
/*
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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5484 KB Output is correct
2 Correct 4 ms 5484 KB Output is correct
3 Correct 4 ms 5484 KB Output is correct
4 Correct 5 ms 5484 KB Output is correct
5 Correct 5 ms 5484 KB Output is correct
6 Correct 9 ms 5612 KB Output is correct
7 Correct 75 ms 7276 KB Output is correct
8 Correct 71 ms 7292 KB Output is correct
9 Correct 72 ms 7276 KB Output is correct
10 Correct 1004 ms 23796 KB Output is correct
11 Correct 1080 ms 23688 KB Output is correct
12 Correct 1751 ms 31584 KB Output is correct
13 Correct 232 ms 23648 KB Output is correct
14 Correct 668 ms 23176 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 27488 KB Output is correct
2 Correct 516 ms 27232 KB Output is correct
3 Correct 741 ms 30860 KB Output is correct
4 Correct 822 ms 30800 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5484 KB Output is correct
2 Correct 4 ms 5484 KB Output is correct
3 Correct 4 ms 5484 KB Output is correct
4 Correct 5 ms 5484 KB Output is correct
5 Correct 5 ms 5484 KB Output is correct
6 Correct 17 ms 5740 KB Output is correct
7 Correct 188 ms 8172 KB Output is correct
8 Correct 2657 ms 32352 KB Output is correct
9 Correct 2694 ms 32352 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2756 ms 32212 KB Output is correct
2 Correct 1549 ms 31840 KB Output is correct
3 Correct 1583 ms 32084 KB Output is correct
4 Correct 1565 ms 32096 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5484 KB Output is correct
2 Correct 4 ms 5484 KB Output is correct
3 Correct 4 ms 5484 KB Output is correct
4 Correct 5 ms 5484 KB Output is correct
5 Correct 16 ms 5612 KB Output is correct
6 Correct 150 ms 7404 KB Output is correct
7 Correct 1714 ms 24944 KB Output is correct
8 Correct 2713 ms 32484 KB Output is correct
9 Correct 560 ms 24824 KB Output is correct
10 Correct 1044 ms 24552 KB Output is correct
11 Correct 1000 ms 28784 KB Output is correct
12 Correct 1004 ms 28784 KB Output is correct
13 Correct 1572 ms 32072 KB Output is correct