oj.uz

Submission #815770

# Submission time Handle Problem Language Result Execution time Memory
815770 2023-08-08T22:12:33 Z Lobo Werewolf (IOI18_werewolf) C++17
100 / 100
 720 ms 128636 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
const int inf = 1e9+10;
const int maxn = 4e5+10;
const int lg = 18;

int n, tin[2][maxn], tout[2][maxn], timer, tr[4*maxn];
int ds[2][maxn], dsz[2][maxn];
pair<int,int> p[2][lg+1][maxn];
vector<pair<int,int>> g[2][maxn];

int find(int id, int v) {
	if(ds[id][v] == v) return v;
	return ds[id][v] = find(id,ds[id][v]);
}

void join(int id, int u, int v, int w) {
	u = find(id,u);
	v = find(id,v);
	if(u == v) return;
	if(dsz[id][u] < dsz[id][v]) swap(u,v);
	//cout << id << " " << u << " " << v << " " << w << endl;

	ds[id][v] = u;
	dsz[id][u]+= dsz[id][v];
	g[id][u].pb(mp(w,v));
	p[id][0][v] = mp(u,w);
}

void dfseulertour(int id, int u, int ant) {
	tin[id][u] = ++timer;
	for(auto V : g[id][u]) if(V.sc != ant) {
		int v = V.sc;
		int w = V.fr;
		dfseulertour(id,v,u);
	}
	tout[id][u] = timer;
}

void upd(int no, int l, int r, int pos, int val) {
	if(l > pos || r < pos) return;
	if(l == r) {
		tr[no] = val;
		return;
	}
	int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
	upd(lc,l,mid,pos,val);
	upd(rc,mid+1,r,pos,val);
	tr[no] = min(tr[lc],tr[rc]);
}

int query(int no, int l, int r, int L, int R) {
	if(l > R || r < L) return inf;
	if(l >= L && r <= R) return tr[no];
	int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
	return min(query(lc,l,mid,L,R),query(rc,mid+1,r,L,R));
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
  // int Q = S.size();
  // std::vector<int> A(Q);
  // for (int i = 0; i < Q; ++i) {
  //   A[i] = 0;
  // }
  // return A;

    n = N;
    for(int i = 0; i < n; i++) {
    	ds[0][i] = ds[1][i] = i;
    	dsz[0][i] = dsz[1][i] = 1;
    	p[0][0][i] = p[1][0][i] = mp(i,i);
    }

    vector<pair<int,pair<int,int>>> edgs0;
    for(int i = 0; i < (int) X.size(); i++) {
    	int u = X[i];
    	int v = Y[i];
    	edgs0.pb(mp(min(u,v),mp(u,v)));
    }

    sort(all(edgs0),greater<pair<int,pair<int,int>>>());

    for(auto X : edgs0) {
    	int w = X.fr;
    	int u = X.sc.fr;
    	int v = X.sc.sc;
    	join(0,u,v,w);
    }

    vector<pair<int,pair<int,int>>> edgs1;
    for(int i = 0; i < (int) X.size(); i++) {
    	int u = X[i];
    	int v = Y[i];
    	edgs1.pb(mp(max(u,v),mp(u,v)));
    }

    sort(all(edgs1));

    for(auto X : edgs1) {
    	int w = X.fr;
    	int u = X.sc.fr;
    	int v = X.sc.sc;
    	join(1,u,v,w);
    }

    for(int id = 0; id <= 1; id++) {
	    for(int b = 1; b <= lg; b++) {
	    	for(int i = 0; i < n; i++) {
	    		p[id][b][i].fr = p[id][b-1][p[id][b-1][i].fr].fr;
	    		if(id == 0) p[id][b][i].sc = min(p[id][b-1][p[id][b-1][i].fr].sc,p[id][b-1][i].sc);
	    		else p[id][b][i].sc = max(p[id][b-1][p[id][b-1][i].fr].sc,p[id][b-1][i].sc);
	    	}
	    }
	}

	timer = 0; dfseulertour(0,find(0,0),-1);
	timer = 0; dfseulertour(1,find(1,0),-1);
	vector<pair<pair<pair<int,int>,pair<int,int>>,int>> qrys;
	for(int i = 0; i < S.size(); i++) {
		int lbs = 0;
		int rbs = 0;
		int s = S[i];

		for(int b = lg; b >= 0; b--) {
			// cout << s << "  " << p[0][s][b].sc << endl;
			if(p[0][b][s].sc >= L[i]) {
				s = p[0][b][s].fr;
			}
		}

		int ls = tin[0][s];
		int rs = tin[0][s];
		lbs = 0;
		rbs = (int) g[0][s].size()-1;
		while(lbs <= rbs) {
			int mid = (lbs+rbs)/2;
			if(g[0][s][mid].fr >= L[i]) {
				rs = tout[0][g[0][s][mid].sc];
				lbs = mid+1;
			}
			else {
				rbs = mid-1;
			}
		}

		// cout << s << " " << ls << " " << rs << endl;

		int e = E[i];

		for(int b = lg; b >= 0; b--) {
			if(p[1][b][e].sc <= R[i]) {
				e = p[1][b][e].fr;
			}
		}

		int le = tin[1][e];
		int re = tin[1][e];
		lbs = 0;
		rbs = (int) g[1][e].size()-1;
		while(lbs <= rbs) {
			int mid = (lbs+rbs)/2;
			if(g[1][e][mid].fr <= R[i]) {
				re = tout[1][g[1][e][mid].sc];
				lbs = mid+1;
			}
			else {
				rbs = mid-1;
			}
		}

		// cout << le << " " << re << endl;

		qrys.pb(mp(mp(mp(le,re),mp(ls,rs)),i));
	}

	for(int i = 0; i < n; i++) {
		qrys.pb(mp(mp(mp(tin[1][i],inf),mp(i,-1)),0));
		upd(1,1,n,tin[0][i],tin[1][i]);
		//cout  << "  " << tin[0][i] << " " << tin[1][i] << endl;
	}

	sort(all(qrys));

	vector<int32_t> ans((int) S.size());
	for(auto X : qrys) {
		if(X.fr.sc.sc == -1) {
			int v = X.fr.sc.fr;
			upd(1,1,n,tin[0][v],inf);
		}
		else {
			int ls = X.fr.sc.fr;
			int rs = X.fr.sc.sc;
			int re = X.fr.fr.sc;
			int idqry = X.sc;

			//cout << query(1,1,n,ls,rs) << endl;
			if(query(1,1,n,ls,rs) <= re) {
				ans[idqry] = 1;
			}
			else {
				ans[idqry] = 0;
			}
		}
	}

	return ans;
}

Compilation message

werewolf.cpp: In function 'void dfseulertour(int, int, int)':
werewolf.cpp:40:7: warning: unused variable 'w' [-Wunused-variable]
   40 |   int w = V.fr;
      |       ^
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:127:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |  for(int i = 0; i < S.size(); i++) {
      |                 ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19412 KB Output is correct
2 Correct 9 ms 19412 KB Output is correct
3 Correct 10 ms 19464 KB Output is correct
4 Correct 10 ms 19340 KB Output is correct
5 Correct 11 ms 19420 KB Output is correct
6 Correct 9 ms 19412 KB Output is correct
7 Correct 10 ms 19412 KB Output is correct
8 Correct 8 ms 19500 KB Output is correct
9 Correct 9 ms 19516 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19412 KB Output is correct
2 Correct 9 ms 19412 KB Output is correct
3 Correct 10 ms 19464 KB Output is correct
4 Correct 10 ms 19340 KB Output is correct
5 Correct 11 ms 19420 KB Output is correct
6 Correct 9 ms 19412 KB Output is correct
7 Correct 10 ms 19412 KB Output is correct
8 Correct 8 ms 19500 KB Output is correct
9 Correct 9 ms 19516 KB Output is correct
10 Correct 15 ms 20980 KB Output is correct
11 Correct 14 ms 20948 KB Output is correct
12 Correct 13 ms 21048 KB Output is correct
13 Correct 16 ms 21060 KB Output is correct
14 Correct 17 ms 20956 KB Output is correct
15 Correct 20 ms 21200 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 632 ms 120204 KB Output is correct
2 Correct 449 ms 118172 KB Output is correct
3 Correct 455 ms 118500 KB Output is correct
4 Correct 486 ms 118764 KB Output is correct
5 Correct 506 ms 118844 KB Output is correct
6 Correct 560 ms 119976 KB Output is correct
7 Correct 556 ms 120156 KB Output is correct
8 Correct 453 ms 118128 KB Output is correct
9 Correct 390 ms 118448 KB Output is correct
10 Correct 394 ms 118808 KB Output is correct
11 Correct 397 ms 118904 KB Output is correct
12 Correct 404 ms 120108 KB Output is correct
13 Correct 524 ms 117092 KB Output is correct
14 Correct 548 ms 116580 KB Output is correct
15 Correct 521 ms 117168 KB Output is correct
16 Correct 549 ms 116708 KB Output is correct
17 Correct 561 ms 120172 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19412 KB Output is correct
2 Correct 9 ms 19412 KB Output is correct
3 Correct 10 ms 19464 KB Output is correct
4 Correct 10 ms 19340 KB Output is correct
5 Correct 11 ms 19420 KB Output is correct
6 Correct 9 ms 19412 KB Output is correct
7 Correct 10 ms 19412 KB Output is correct
8 Correct 8 ms 19500 KB Output is correct
9 Correct 9 ms 19516 KB Output is correct
10 Correct 15 ms 20980 KB Output is correct
11 Correct 14 ms 20948 KB Output is correct
12 Correct 13 ms 21048 KB Output is correct
13 Correct 16 ms 21060 KB Output is correct
14 Correct 17 ms 20956 KB Output is correct
15 Correct 20 ms 21200 KB Output is correct
16 Correct 632 ms 120204 KB Output is correct
17 Correct 449 ms 118172 KB Output is correct
18 Correct 455 ms 118500 KB Output is correct
19 Correct 486 ms 118764 KB Output is correct
20 Correct 506 ms 118844 KB Output is correct
21 Correct 560 ms 119976 KB Output is correct
22 Correct 556 ms 120156 KB Output is correct
23 Correct 453 ms 118128 KB Output is correct
24 Correct 390 ms 118448 KB Output is correct
25 Correct 394 ms 118808 KB Output is correct
26 Correct 397 ms 118904 KB Output is correct
27 Correct 404 ms 120108 KB Output is correct
28 Correct 524 ms 117092 KB Output is correct
29 Correct 548 ms 116580 KB Output is correct
30 Correct 521 ms 117168 KB Output is correct
31 Correct 549 ms 116708 KB Output is correct
32 Correct 561 ms 120172 KB Output is correct
33 Correct 565 ms 119832 KB Output is correct
34 Correct 354 ms 51028 KB Output is correct
35 Correct 578 ms 119744 KB Output is correct
36 Correct 598 ms 120116 KB Output is correct
37 Correct 557 ms 119596 KB Output is correct
38 Correct 568 ms 120236 KB Output is correct
39 Correct 588 ms 118840 KB Output is correct
40 Correct 693 ms 128400 KB Output is correct
41 Correct 452 ms 119552 KB Output is correct
42 Correct 412 ms 120028 KB Output is correct
43 Correct 517 ms 124696 KB Output is correct
44 Correct 491 ms 119632 KB Output is correct
45 Correct 432 ms 119168 KB Output is correct
46 Correct 450 ms 118820 KB Output is correct
47 Correct 534 ms 116912 KB Output is correct
48 Correct 522 ms 116904 KB Output is correct
49 Correct 529 ms 117212 KB Output is correct
50 Correct 594 ms 116772 KB Output is correct
51 Correct 611 ms 128636 KB Output is correct
52 Correct 720 ms 128496 KB Output is correct