oj.uz

Submission #815764

# Submission time Handle Problem Language Result Execution time Memory
815764 2023-08-08T21:34:49 Z Lobo Werewolf (IOI18_werewolf) C++17
100 / 100
 684 ms 146152 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][maxn][lg+1];
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][v][0] = 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][i][0] = p[1][i][0] = 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][i][b].fr = p[id][p[id][i][b-1].fr][b-1].fr;
	    		if(id == 0) p[id][i][b].sc = min(p[id][p[id][i][b-1].fr][b-1].sc,p[id][i][b-1].sc);
	    		else p[id][i][b].sc = max(p[id][p[id][i][b-1].fr][b-1].sc,p[id][i][b-1].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][s][b].sc >= L[i]) {
				s = p[0][s][b].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][e][b].sc <= R[i]) {
				e = p[1][e][b].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 10 ms 19156 KB Output is correct
2 Correct 10 ms 19228 KB Output is correct
3 Correct 10 ms 19200 KB Output is correct
4 Correct 11 ms 19104 KB Output is correct
5 Correct 10 ms 19228 KB Output is correct
6 Correct 10 ms 19144 KB Output is correct
7 Correct 10 ms 19156 KB Output is correct
8 Correct 10 ms 19224 KB Output is correct
9 Correct 10 ms 19224 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 10 ms 19228 KB Output is correct
3 Correct 10 ms 19200 KB Output is correct
4 Correct 11 ms 19104 KB Output is correct
5 Correct 10 ms 19228 KB Output is correct
6 Correct 10 ms 19144 KB Output is correct
7 Correct 10 ms 19156 KB Output is correct
8 Correct 10 ms 19224 KB Output is correct
9 Correct 10 ms 19224 KB Output is correct
10 Correct 15 ms 20900 KB Output is correct
11 Correct 16 ms 20904 KB Output is correct
12 Correct 16 ms 20956 KB Output is correct
13 Correct 15 ms 20900 KB Output is correct
14 Correct 15 ms 20948 KB Output is correct
15 Correct 16 ms 21160 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 134592 KB Output is correct
2 Correct 572 ms 132584 KB Output is correct
3 Correct 574 ms 132828 KB Output is correct
4 Correct 589 ms 133208 KB Output is correct
5 Correct 587 ms 133376 KB Output is correct
6 Correct 622 ms 134352 KB Output is correct
7 Correct 597 ms 134508 KB Output is correct
8 Correct 527 ms 132612 KB Output is correct
9 Correct 493 ms 132892 KB Output is correct
10 Correct 496 ms 133148 KB Output is correct
11 Correct 511 ms 133200 KB Output is correct
12 Correct 513 ms 134472 KB Output is correct
13 Correct 576 ms 131508 KB Output is correct
14 Correct 569 ms 131052 KB Output is correct
15 Correct 590 ms 131656 KB Output is correct
16 Correct 571 ms 131036 KB Output is correct
17 Correct 598 ms 134548 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 10 ms 19228 KB Output is correct
3 Correct 10 ms 19200 KB Output is correct
4 Correct 11 ms 19104 KB Output is correct
5 Correct 10 ms 19228 KB Output is correct
6 Correct 10 ms 19144 KB Output is correct
7 Correct 10 ms 19156 KB Output is correct
8 Correct 10 ms 19224 KB Output is correct
9 Correct 10 ms 19224 KB Output is correct
10 Correct 15 ms 20900 KB Output is correct
11 Correct 16 ms 20904 KB Output is correct
12 Correct 16 ms 20956 KB Output is correct
13 Correct 15 ms 20900 KB Output is correct
14 Correct 15 ms 20948 KB Output is correct
15 Correct 16 ms 21160 KB Output is correct
16 Correct 611 ms 134592 KB Output is correct
17 Correct 572 ms 132584 KB Output is correct
18 Correct 574 ms 132828 KB Output is correct
19 Correct 589 ms 133208 KB Output is correct
20 Correct 587 ms 133376 KB Output is correct
21 Correct 622 ms 134352 KB Output is correct
22 Correct 597 ms 134508 KB Output is correct
23 Correct 527 ms 132612 KB Output is correct
24 Correct 493 ms 132892 KB Output is correct
25 Correct 496 ms 133148 KB Output is correct
26 Correct 511 ms 133200 KB Output is correct
27 Correct 513 ms 134472 KB Output is correct
28 Correct 576 ms 131508 KB Output is correct
29 Correct 569 ms 131052 KB Output is correct
30 Correct 590 ms 131656 KB Output is correct
31 Correct 571 ms 131036 KB Output is correct
32 Correct 598 ms 134548 KB Output is correct
33 Correct 609 ms 134180 KB Output is correct
34 Correct 351 ms 62388 KB Output is correct
35 Correct 619 ms 134404 KB Output is correct
36 Correct 625 ms 134588 KB Output is correct
37 Correct 634 ms 134184 KB Output is correct
38 Correct 660 ms 134828 KB Output is correct
39 Correct 584 ms 133212 KB Output is correct
40 Correct 640 ms 145912 KB Output is correct
41 Correct 625 ms 133960 KB Output is correct
42 Correct 505 ms 134568 KB Output is correct
43 Correct 583 ms 140660 KB Output is correct
44 Correct 594 ms 134240 KB Output is correct
45 Correct 508 ms 133664 KB Output is correct
46 Correct 533 ms 133336 KB Output is correct
47 Correct 567 ms 131440 KB Output is correct
48 Correct 559 ms 131272 KB Output is correct
49 Correct 591 ms 131728 KB Output is correct
50 Correct 579 ms 131172 KB Output is correct
51 Correct 659 ms 146152 KB Output is correct
52 Correct 684 ms 146032 KB Output is correct