oj.uz

Submission #1090120

# Submission time Handle Problem Language Result Execution time Memory
1090120 2024-09-17T18:13:30 Z StefanSebez Werewolf (IOI18_werewolf) C++14
100 / 100
 461 ms 116372 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=2e5+50,lg=19;
struct DSU{
	int par[N+50],in[N+50],out[N+50],nc,a[N+50],Par[N+50][lg+1],sajz[N+50];
	vector<int>E[N+50];
	void Init(){for(int i=0;i<=N;i++)par[i]=i,nc=0,sajz[i]=1;}
	int FS(int u){return par[u]==u?u:par[u]=FS(par[u]);}
	void US(int u,int v){par[FS(u)]=FS(v);}
	void AddEdge(int u,int v){if(u!=v) E[u].pb(v),E[v].pb(u);}
	void DFS(int u,int parent){
		in[u]=++nc;a[nc]=u;Par[u][0]=parent;
		for(int i=1;i<=lg;i++) Par[u][i]=Par[Par[u][i-1]][i-1];
		for(auto i:E[u]) if(i!=parent) DFS(i,u);
		out[u]=nc;
	}
	int NadjiL(int u,int x){for(int i=lg;i>=0;i--) if(Par[u][i] && Par[u][i]<=x) u=Par[u][i];return u;}
	int NadjiR(int u,int x){for(int i=lg;i>=0;i--) if(Par[u][i]>=x) u=Par[u][i];return u;}
}dsu[2];
vector<int>E[N+50];
vector<array<int,5> >ev[N+50];
int ind[N+50];
int T[N+50];
void Update(int i,int qval){for(;i<=N;i+=i&-i)T[i]+=qval;}
int Get(int i){int res=0;for(;i>=1;i-=i&-i)res+=T[i];return res;}
std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,std::vector<int> U, std::vector<int> V,std::vector<int> L, std::vector<int> R) {
	int q=U.size();
	for(int i=0;i<q;i++) U[i]++,V[i]++,L[i]++,R[i]++;
	for(int i=0;i<X.size();i++){X[i]++,Y[i]++;int u=X[i],v=Y[i];E[u].pb(v);E[v].pb(u);}
	dsu[0].Init(),dsu[1].Init();
	for(int i=1;i<=n;i++) for(auto j:E[i]) if(j<i && dsu[0].FS(j)!=dsu[0].FS(i)) {dsu[0].AddEdge(dsu[0].FS(j),i);dsu[0].US(j,i);}
	dsu[0].DFS(n,0);
	for(int i=n;i>=1;i--) for(auto j:E[i]) if(j>i && dsu[1].FS(j)!=dsu[1].FS(i)) {dsu[1].AddEdge(dsu[1].FS(j),i);dsu[1].US(j,i);}
	dsu[1].DFS(1,0);
	for(int i=1;i<=n;i++) ind[dsu[1].a[i]]=i;
	vector<int>res(q,0);
	for(int I=0;I<q;I++){
		int u=U[I],v=V[I],l=L[I],r=R[I];
		int v1=dsu[0].NadjiL(v,r),u1=dsu[1].NadjiR(u,l);
		ev[dsu[0].in[v1]-1].pb({dsu[1].in[u1],dsu[1].out[u1],I,-1});
		ev[dsu[0].out[v1]].pb({dsu[1].in[u1],dsu[1].out[u1],I,1});
	}
	for(int i=1;i<=n;i++){
		Update(ind[dsu[0].a[i]],1);
		for(auto j:ev[i]){
			int bul=j[3];
			res[j[2]]+=bul*(Get(j[1])-Get(j[0]-1));
		}
	}
	for(int i=0;i<q;i++) if(res[i]) res[i]=1;
	return res;
}

Compilation message

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:35:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i=0;i<X.size();i++){X[i]++,Y[i]++;int u=X[i],v=Y[i];E[u].pb(v);E[v].pb(u);}
      |              ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22360 KB Output is correct
2 Correct 10 ms 22364 KB Output is correct
3 Correct 10 ms 22364 KB Output is correct
4 Correct 16 ms 22360 KB Output is correct
5 Correct 10 ms 22364 KB Output is correct
6 Correct 9 ms 22420 KB Output is correct
7 Correct 9 ms 22364 KB Output is correct
8 Correct 14 ms 22364 KB Output is correct
9 Correct 10 ms 22364 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22360 KB Output is correct
2 Correct 10 ms 22364 KB Output is correct
3 Correct 10 ms 22364 KB Output is correct
4 Correct 16 ms 22360 KB Output is correct
5 Correct 10 ms 22364 KB Output is correct
6 Correct 9 ms 22420 KB Output is correct
7 Correct 9 ms 22364 KB Output is correct
8 Correct 14 ms 22364 KB Output is correct
9 Correct 10 ms 22364 KB Output is correct
10 Correct 15 ms 23644 KB Output is correct
11 Correct 14 ms 23588 KB Output is correct
12 Correct 14 ms 23644 KB Output is correct
13 Correct 19 ms 23656 KB Output is correct
14 Correct 14 ms 23616 KB Output is correct
15 Correct 14 ms 23640 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 108416 KB Output is correct
2 Correct 401 ms 110980 KB Output is correct
3 Correct 399 ms 109588 KB Output is correct
4 Correct 351 ms 108628 KB Output is correct
5 Correct 365 ms 108368 KB Output is correct
6 Correct 382 ms 108048 KB Output is correct
7 Correct 395 ms 106280 KB Output is correct
8 Correct 358 ms 110864 KB Output is correct
9 Correct 338 ms 109680 KB Output is correct
10 Correct 296 ms 107152 KB Output is correct
11 Correct 312 ms 108292 KB Output is correct
12 Correct 324 ms 108156 KB Output is correct
13 Correct 414 ms 109940 KB Output is correct
14 Correct 396 ms 109932 KB Output is correct
15 Correct 385 ms 109936 KB Output is correct
16 Correct 382 ms 109940 KB Output is correct
17 Correct 395 ms 105960 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22360 KB Output is correct
2 Correct 10 ms 22364 KB Output is correct
3 Correct 10 ms 22364 KB Output is correct
4 Correct 16 ms 22360 KB Output is correct
5 Correct 10 ms 22364 KB Output is correct
6 Correct 9 ms 22420 KB Output is correct
7 Correct 9 ms 22364 KB Output is correct
8 Correct 14 ms 22364 KB Output is correct
9 Correct 10 ms 22364 KB Output is correct
10 Correct 15 ms 23644 KB Output is correct
11 Correct 14 ms 23588 KB Output is correct
12 Correct 14 ms 23644 KB Output is correct
13 Correct 19 ms 23656 KB Output is correct
14 Correct 14 ms 23616 KB Output is correct
15 Correct 14 ms 23640 KB Output is correct
16 Correct 425 ms 108416 KB Output is correct
17 Correct 401 ms 110980 KB Output is correct
18 Correct 399 ms 109588 KB Output is correct
19 Correct 351 ms 108628 KB Output is correct
20 Correct 365 ms 108368 KB Output is correct
21 Correct 382 ms 108048 KB Output is correct
22 Correct 395 ms 106280 KB Output is correct
23 Correct 358 ms 110864 KB Output is correct
24 Correct 338 ms 109680 KB Output is correct
25 Correct 296 ms 107152 KB Output is correct
26 Correct 312 ms 108292 KB Output is correct
27 Correct 324 ms 108156 KB Output is correct
28 Correct 414 ms 109940 KB Output is correct
29 Correct 396 ms 109932 KB Output is correct
30 Correct 385 ms 109936 KB Output is correct
31 Correct 382 ms 109940 KB Output is correct
32 Correct 395 ms 105960 KB Output is correct
33 Correct 453 ms 109652 KB Output is correct
34 Correct 184 ms 63248 KB Output is correct
35 Correct 454 ms 111360 KB Output is correct
36 Correct 415 ms 108972 KB Output is correct
37 Correct 461 ms 110936 KB Output is correct
38 Correct 435 ms 109524 KB Output is correct
39 Correct 376 ms 113624 KB Output is correct
40 Correct 449 ms 114956 KB Output is correct
41 Correct 348 ms 109104 KB Output is correct
42 Correct 310 ms 107860 KB Output is correct
43 Correct 415 ms 114696 KB Output is correct
44 Correct 410 ms 110684 KB Output is correct
45 Correct 372 ms 113644 KB Output is correct
46 Correct 374 ms 113368 KB Output is correct
47 Correct 422 ms 110196 KB Output is correct
48 Correct 399 ms 109964 KB Output is correct
49 Correct 395 ms 110148 KB Output is correct
50 Correct 401 ms 110000 KB Output is correct
51 Correct 426 ms 116192 KB Output is correct
52 Correct 438 ms 116372 KB Output is correct