oj.uz

Submission #288144

# Submission time Handle Problem Language Result Execution time Memory
288144 2020-09-01T09:04:54 Z Noam13 Werewolf (IOI18_werewolf) C++14
100 / 100
 1644 ms 191840 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vi>
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define pb push_back
#define ii pair<int, int>
#define vii vector<ii>
#define vvii vector<vii>
#define x first
#define y second
#define all(a) a.begin(),a.end()
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a = min(a,b)
using namespace std;


struct DSU{
	int n;
	vi p, sz;
	DSU(int n=0): n(n), p(n,-1), sz(n,1){}
	void init(int nn){
		n = nn;
		p.clear(); sz.clear(); 
		p.resize(n,-1); sz.resize(n,1);
	}
	int find(int c){
		if (p[c]==-1) return c;
		return p[c] = find(p[c]);
	}
	bool uni(int a, int b){
		a = find(a), b = find(b);
		if (a==b) return 0;
		//if (sz[a]>sz[b]) swap(a,b);
		p[a] = b;
		sz[b] += sz[a];
		return 1;
	}
};
const int INF = 1e9;
struct BINARY{
	int n, log;
	vvii g;
	vvi anc, mine;
	vi order, pos;
	vi in, out;
	int t = 0;
	BINARY(vvii& _g, int s=0): g(_g), n(_g.size()){
		for(log=1; (1<<log)<n;log++);
		anc.resize(n, vi(log, -1));
		mine.resize(n, vi(log, -INF));
		in.resize(n); out.resize(n);
		dfs(s);
		pos.resize(n);
		loop(i,0,n) pos[order[i]] = i;
	}
	void dfs(int cur, int p=-1, int pw=-INF){
		order.pb(cur); in[cur] = t++;
		anc[cur][0] = p; mine[cur][0] = pw;
		loop(i,1,log){
			if (anc[cur][i-1]==-1) break;
			anc[cur][i] = anc[anc[cur][i-1]][i-1];
			mine[cur][i] = min(mine[cur][i-1], mine[anc[cur][i-1]][i-1]);
		}
		for(auto nei:g[cur]) if(nei.x!=p){
			dfs(nei.x, cur, nei.y);
		}
		out[cur] = t-1;
	}
	int lift(int cur, int L){
		loopr(i,0,log){
			if (mine[cur][i]>=L){
				cur = anc[cur][i];
			}
		}
		return cur;
	}
};
struct Qur{
	int x, l, r;
	int ind; bool in;
	bool operator<(const Qur& a){
		return x < a.x;
	}
};
struct SEG{
	int sz;
	vi a;
	SEG(int n){
		for(sz=1;sz<n;sz*=2);
		a.resize(2*sz);
	}
	void update(int i, int x){
		a[i+=sz]=x;
		for(i/=2;i;i/=2) a[i] = a[2*i] + a[2*i+1];
	}
	int query(int l, int r){
		int ans =  0;
		for(l+=sz, r+=sz; l<=r; l/=2, r/=2){
			if (l%2) ans+=a[l++];
			if (r%2==0) ans+=a[r--];
		}
		return ans;
	}
};
vi check_validity(int N, vi u, vi v, vi S, vi E, vi L, vi R) {
	int n = N, m = u.size(), q=S.size();
	
	vvi g(n);
	loop(i,0,m){
		int a = u[i], b = v[i];
		g[a].pb(b);
		g[b].pb(a);
	}
	vector<ii> mine, maxe;
	DSU dsu(n);
	loopr(i,0,n){
		for(auto j:g[i]){
			if (j<i) continue;
			int x = dsu.find(j);
			if (x!=i){
				mine.pb({x,i});
				dsu.p[x] = i;
			} 
		}
	}
	dsu.init(n);
	loop(i,0,n){
		for(auto j:g[i]){
			if (j>i) continue;
			int x = dsu.find(j);
			if (x!=i){
				maxe.pb({x,i});
				dsu.p[x] = i;
			} 
		}
	}
	vvii gs(n), ge(n);
	for(auto e:mine){
		gs[e.x].pb({e.y, min(e.x, e.y)});
		gs[e.y].pb({e.x, min(e.x, e.y)});
	}
	for(auto e:maxe){
		//cout<<e.x<<" "<<e.y<<endl;
		ge[e.x].pb({e.y, -max(e.x, e.y)});
		ge[e.y].pb({e.x, -max(e.x, e.y)});
	}
	BINARY bins(gs, 0), bine(ge, n-1);
	//loop(i,0,n) cout<<bine.order[i]<<" "; cout<<endl;
	vector<Qur> eve;
	loop(i,0,q){
		int a = bins.lift(S[i], L[i]), b = bine.lift(E[i], -R[i]);
		eve.pb({bins.in[a]-1, bine.in[b], bine.out[b], i, 1});
		eve.pb({bins.out[a], bine.in[b], bine.out[b], i, 0});
		//cout<<"AB: "<<a<<" "<<b<<endl;
		//cout<<bine.in[b]<< " " << bine.out[b] << endl;
		//cout<<bins.in[a]<< " " << bins.out[a] << endl;
	}
	sort(all(eve));
	SEG seg(n);
	vi ans(q); int ind = 0;
	for(auto &e:eve){
		while(ind<=e.x){
			seg.update(bine.pos[bins.order[ind]], 1);
			ind++;
		}
		int v = seg.query(e.l, e.r);
		//cout<<"V: "<<v<<endl;
		ans[e.ind]+=(e.in?-v:v);
	}
	loop(i,0,q) if(ans[i]>0) ans[i]=1;
	return ans;
}
/*
clear
g++ werewolf.cpp grader.cpp -o a ; ./a
10 9 1
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
8 9 3 9
*/

Compilation message

werewolf.cpp: In constructor 'BINARY::BINARY(std::vector<std::vector<std::pair<int, int> > >&, int)':
werewolf.cpp:44:7: warning: 'BINARY::g' will be initialized after [-Wreorder]
   44 |  vvii g;
      |       ^
werewolf.cpp:43:6: warning:   'int BINARY::n' [-Wreorder]
   43 |  int n, log;
      |      ^
werewolf.cpp:49:2: warning:   when initialized here [-Wreorder]
   49 |  BINARY(vvii& _g, int s=0): g(_g), n(_g.size()){
      |  ^~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 11 ms 2944 KB Output is correct
11 Correct 11 ms 2944 KB Output is correct
12 Correct 11 ms 2916 KB Output is correct
13 Correct 11 ms 3072 KB Output is correct
14 Correct 10 ms 3072 KB Output is correct
15 Correct 12 ms 3044 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1244 ms 179248 KB Output is correct
2 Correct 1595 ms 183736 KB Output is correct
3 Correct 1356 ms 180572 KB Output is correct
4 Correct 1176 ms 179292 KB Output is correct
5 Correct 1175 ms 179416 KB Output is correct
6 Correct 1231 ms 179156 KB Output is correct
7 Correct 1187 ms 179160 KB Output is correct
8 Correct 1417 ms 184084 KB Output is correct
9 Correct 1067 ms 180696 KB Output is correct
10 Correct 858 ms 179420 KB Output is correct
11 Correct 919 ms 179292 KB Output is correct
12 Correct 1010 ms 179168 KB Output is correct
13 Correct 1632 ms 183260 KB Output is correct
14 Correct 1608 ms 183464 KB Output is correct
15 Correct 1603 ms 183384 KB Output is correct
16 Correct 1611 ms 183260 KB Output is correct
17 Correct 1160 ms 179036 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 11 ms 2944 KB Output is correct
11 Correct 11 ms 2944 KB Output is correct
12 Correct 11 ms 2916 KB Output is correct
13 Correct 11 ms 3072 KB Output is correct
14 Correct 10 ms 3072 KB Output is correct
15 Correct 12 ms 3044 KB Output is correct
16 Correct 1244 ms 179248 KB Output is correct
17 Correct 1595 ms 183736 KB Output is correct
18 Correct 1356 ms 180572 KB Output is correct
19 Correct 1176 ms 179292 KB Output is correct
20 Correct 1175 ms 179416 KB Output is correct
21 Correct 1231 ms 179156 KB Output is correct
22 Correct 1187 ms 179160 KB Output is correct
23 Correct 1417 ms 184084 KB Output is correct
24 Correct 1067 ms 180696 KB Output is correct
25 Correct 858 ms 179420 KB Output is correct
26 Correct 919 ms 179292 KB Output is correct
27 Correct 1010 ms 179168 KB Output is correct
28 Correct 1632 ms 183260 KB Output is correct
29 Correct 1608 ms 183464 KB Output is correct
30 Correct 1603 ms 183384 KB Output is correct
31 Correct 1611 ms 183260 KB Output is correct
32 Correct 1160 ms 179036 KB Output is correct
33 Correct 1403 ms 181024 KB Output is correct
34 Correct 469 ms 41568 KB Output is correct
35 Correct 1574 ms 183900 KB Output is correct
36 Correct 1306 ms 180064 KB Output is correct
37 Correct 1536 ms 183164 KB Output is correct
38 Correct 1387 ms 180840 KB Output is correct
39 Correct 1389 ms 191840 KB Output is correct
40 Correct 1624 ms 188508 KB Output is correct
41 Correct 1258 ms 182612 KB Output is correct
42 Correct 1035 ms 179932 KB Output is correct
43 Correct 1644 ms 187744 KB Output is correct
44 Correct 1435 ms 183340 KB Output is correct
45 Correct 1219 ms 191836 KB Output is correct
46 Correct 1251 ms 191580 KB Output is correct
47 Correct 1619 ms 183512 KB Output is correct
48 Correct 1584 ms 183392 KB Output is correct
49 Correct 1622 ms 183388 KB Output is correct
50 Correct 1596 ms 183260 KB Output is correct
51 Correct 1508 ms 189384 KB Output is correct
52 Correct 1502 ms 189432 KB Output is correct