oj.uz

Submission #815769

# Submission time Handle Problem Language Result Execution time Memory
815769 2023-08-08T22:12:11 Z Lobo Werewolf (IOI18_werewolf) C++17
100 / 100
 651 ms 134996 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 = 20;

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 19540 KB Output is correct
2 Correct 9 ms 19520 KB Output is correct
3 Correct 10 ms 19516 KB Output is correct
4 Correct 12 ms 19464 KB Output is correct
5 Correct 10 ms 19540 KB Output is correct
6 Correct 10 ms 19540 KB Output is correct
7 Correct 10 ms 19548 KB Output is correct
8 Correct 10 ms 19552 KB Output is correct
9 Correct 9 ms 19540 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19540 KB Output is correct
2 Correct 9 ms 19520 KB Output is correct
3 Correct 10 ms 19516 KB Output is correct
4 Correct 12 ms 19464 KB Output is correct
5 Correct 10 ms 19540 KB Output is correct
6 Correct 10 ms 19540 KB Output is correct
7 Correct 10 ms 19548 KB Output is correct
8 Correct 10 ms 19552 KB Output is correct
9 Correct 9 ms 19540 KB Output is correct
10 Correct 14 ms 21192 KB Output is correct
11 Correct 14 ms 21060 KB Output is correct
12 Correct 15 ms 21140 KB Output is correct
13 Correct 15 ms 21204 KB Output is correct
14 Correct 15 ms 21084 KB Output is correct
15 Correct 15 ms 21332 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 126576 KB Output is correct
2 Correct 459 ms 124460 KB Output is correct
3 Correct 462 ms 124760 KB Output is correct
4 Correct 499 ms 125084 KB Output is correct
5 Correct 528 ms 125156 KB Output is correct
6 Correct 572 ms 126304 KB Output is correct
7 Correct 604 ms 126452 KB Output is correct
8 Correct 435 ms 124396 KB Output is correct
9 Correct 404 ms 124756 KB Output is correct
10 Correct 388 ms 125036 KB Output is correct
11 Correct 404 ms 125116 KB Output is correct
12 Correct 410 ms 126316 KB Output is correct
13 Correct 543 ms 123444 KB Output is correct
14 Correct 542 ms 122900 KB Output is correct
15 Correct 545 ms 123480 KB Output is correct
16 Correct 580 ms 122968 KB Output is correct
17 Correct 550 ms 126432 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19540 KB Output is correct
2 Correct 9 ms 19520 KB Output is correct
3 Correct 10 ms 19516 KB Output is correct
4 Correct 12 ms 19464 KB Output is correct
5 Correct 10 ms 19540 KB Output is correct
6 Correct 10 ms 19540 KB Output is correct
7 Correct 10 ms 19548 KB Output is correct
8 Correct 10 ms 19552 KB Output is correct
9 Correct 9 ms 19540 KB Output is correct
10 Correct 14 ms 21192 KB Output is correct
11 Correct 14 ms 21060 KB Output is correct
12 Correct 15 ms 21140 KB Output is correct
13 Correct 15 ms 21204 KB Output is correct
14 Correct 15 ms 21084 KB Output is correct
15 Correct 15 ms 21332 KB Output is correct
16 Correct 651 ms 126576 KB Output is correct
17 Correct 459 ms 124460 KB Output is correct
18 Correct 462 ms 124760 KB Output is correct
19 Correct 499 ms 125084 KB Output is correct
20 Correct 528 ms 125156 KB Output is correct
21 Correct 572 ms 126304 KB Output is correct
22 Correct 604 ms 126452 KB Output is correct
23 Correct 435 ms 124396 KB Output is correct
24 Correct 404 ms 124756 KB Output is correct
25 Correct 388 ms 125036 KB Output is correct
26 Correct 404 ms 125116 KB Output is correct
27 Correct 410 ms 126316 KB Output is correct
28 Correct 543 ms 123444 KB Output is correct
29 Correct 542 ms 122900 KB Output is correct
30 Correct 545 ms 123480 KB Output is correct
31 Correct 580 ms 122968 KB Output is correct
32 Correct 550 ms 126432 KB Output is correct
33 Correct 594 ms 126080 KB Output is correct
34 Correct 330 ms 51096 KB Output is correct
35 Correct 546 ms 125968 KB Output is correct
36 Correct 604 ms 126440 KB Output is correct
37 Correct 558 ms 125944 KB Output is correct
38 Correct 579 ms 126480 KB Output is correct
39 Correct 519 ms 125176 KB Output is correct
40 Correct 613 ms 134736 KB Output is correct
41 Correct 458 ms 125824 KB Output is correct
42 Correct 415 ms 126392 KB Output is correct
43 Correct 520 ms 130916 KB Output is correct
44 Correct 486 ms 125872 KB Output is correct
45 Correct 434 ms 125408 KB Output is correct
46 Correct 459 ms 125160 KB Output is correct
47 Correct 558 ms 123204 KB Output is correct
48 Correct 566 ms 123172 KB Output is correct
49 Correct 568 ms 123584 KB Output is correct
50 Correct 576 ms 123032 KB Output is correct
51 Correct 592 ms 134996 KB Output is correct
52 Correct 645 ms 134788 KB Output is correct