oj.uz

Submission #955156

# Submission time Handle Problem Language Result Execution time Memory
955156 2024-03-29T13:37:48 Z djs100201 Werewolf (IOI18_werewolf) C++17
100 / 100
 652 ms 203244 KB 
#include<bits/stdc++.h>
#include<werewolf.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ =4e5+100, inf = (ll)2e9 * (ll)1e9 + 7, mod = 1e9+7;
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k;
ll gcd(ll x,ll y){
	if(!y)return x;
	return gcd(y,x%y);
}
//ctrl + g ->줄이동
 
class seg{
	public:
	vector<ll>tree;
	ll base;
	seg(int n){
		for(base=1;base<=n;base*=2);
		//0~n쓰겠다
		tree.resize(n*4+4,-inf);
	}
	ll f(ll l,ll r){
		l+=base,r+=base;
		ll ret=-inf;
		while(l<=r){
			if(l%2)ret=max(ret,tree[l++]);
			if(!(r%2))ret=max(ret,tree[r--]);
			l/=2,r/=2;
		}
		return ret;
	}
	void update(ll i,ll v){
		i+=base;
		tree[i]=max(tree[i],v);
		i/=2;
		while(i){
			tree[i]=max(tree[i*2],tree[i*2+1]);
			i/=2;
		}
	}
};
class UF{
	public:
	vector<int>par;
	UF(int n){
		par.resize(n+1);
		for(int i=0;i<=n;i++)par[i]=-1;
	}
	int find(int x){
		if(par[x]==-1)return x;
		return par[x]=find(par[x]);
	}
	void merge(int x,int y){
		x=find(x),y=find(y);
		if(x==y)return;
		par[x]=y;
	}
};
class graph{
	public:
	vector<vector<ll>>edge;
	vector<ll>in,out;
	int cnt;
	graph(int n){
		edge.resize(n+1);
		in.resize(n+1);
		out.resize(n+1);
		cnt=0;
	}
	void add_edge(int u,int v){
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	void dfs(ll x,ll par){
		in[x]=cnt++;
		for(auto nxt:edge[x]){
			if(nxt==par)continue;
			dfs(nxt,x);
		}
		out[x]=cnt-1;
	}
};
vector<ll>v1[n_],v2[n_],LQ[n_],RQ[n_],XX[n_],XQ[n_];
ll Lidx[n_],Ridx[n_];
vector<P>YQ[n_];
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R){
	n=N;
	ll q=L.size();
	vector<int>ret(q);
	for(int i=0;i<q;i++){
		LQ[L[i]].push_back(i);
		RQ[R[i]].push_back(i);
	}
	for(int i=0;i<X.size();i++){
		if(X[i]>Y[i])swap(X[i],Y[i]);
		v1[X[i]].push_back(Y[i]);
		v2[Y[i]].push_back(X[i]);
	}
	
	UF LL(2*n),RR(2*n);
	graph LG(2*n),RG(2*n);
 
	base=n;
	for(int i=n-1;i>=0;i--){
		for(auto nxt:v1[i]){
          	a=LL.find(i),nxt=LL.find(nxt);
			if(a==nxt)continue;
			LG.add_edge(a,base),LG.add_edge(nxt,base);
			LL.merge(a,base),LL.merge(nxt,base);
			base++;
		}
		for(auto nxt:LQ[i])Lidx[nxt]=LL.find(S[nxt]);
	}
	LG.dfs(base-1,-1);
	base=n;
	for(int i=0;i<n;i++){
		for(auto nxt:v2[i]){
          	a=RR.find(i),nxt=RR.find(nxt);
			if(a==nxt)continue;
			RG.add_edge(a,base),RG.add_edge(nxt,base);
			RR.merge(a,base),RR.merge(nxt,base);
			base++;
		}
		for(auto nxt:RQ[i])Ridx[nxt]=RR.find(E[nxt]);
	}
	RG.dfs(base-1,-1);
	for(int i=0;i<n;i++)XX[LG.in[i]].push_back(RG.in[i]);
	for(int i=0;i<q;i++)XQ[LG.out[Lidx[i]]].push_back(i);
	seg seg_(n*2+100);
	for(int i=0;i<n_;i++){
		for(auto nxt:XX[i])seg_.update(nxt,i);
		for(auto nxt:XQ[i]){
			if(LG.in[Lidx[nxt]]<=seg_.f(RG.in[Ridx[nxt]],RG.out[Ridx[nxt]]))ret[nxt]=1;
			else ret[nxt]=0;
		}
	}
	return ret;
}

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 70244 KB Output is correct
2 Correct 18 ms 70236 KB Output is correct
3 Correct 18 ms 70240 KB Output is correct
4 Correct 17 ms 70388 KB Output is correct
5 Correct 18 ms 70396 KB Output is correct
6 Correct 18 ms 70336 KB Output is correct
7 Correct 17 ms 70460 KB Output is correct
8 Correct 17 ms 70236 KB Output is correct
9 Correct 17 ms 70488 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 70244 KB Output is correct
2 Correct 18 ms 70236 KB Output is correct
3 Correct 18 ms 70240 KB Output is correct
4 Correct 17 ms 70388 KB Output is correct
5 Correct 18 ms 70396 KB Output is correct
6 Correct 18 ms 70336 KB Output is correct
7 Correct 17 ms 70460 KB Output is correct
8 Correct 17 ms 70236 KB Output is correct
9 Correct 17 ms 70488 KB Output is correct
10 Correct 23 ms 72284 KB Output is correct
11 Correct 22 ms 72028 KB Output is correct
12 Correct 24 ms 72036 KB Output is correct
13 Correct 24 ms 72284 KB Output is correct
14 Correct 23 ms 72124 KB Output is correct
15 Correct 23 ms 72292 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 190060 KB Output is correct
2 Correct 480 ms 196428 KB Output is correct
3 Correct 499 ms 194644 KB Output is correct
4 Correct 527 ms 193864 KB Output is correct
5 Correct 530 ms 193644 KB Output is correct
6 Correct 574 ms 194036 KB Output is correct
7 Correct 578 ms 191520 KB Output is correct
8 Correct 459 ms 196432 KB Output is correct
9 Correct 460 ms 193088 KB Output is correct
10 Correct 466 ms 192100 KB Output is correct
11 Correct 485 ms 192472 KB Output is correct
12 Correct 531 ms 192848 KB Output is correct
13 Correct 453 ms 199996 KB Output is correct
14 Correct 453 ms 199812 KB Output is correct
15 Correct 438 ms 199936 KB Output is correct
16 Correct 474 ms 199896 KB Output is correct
17 Correct 569 ms 191120 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 70244 KB Output is correct
2 Correct 18 ms 70236 KB Output is correct
3 Correct 18 ms 70240 KB Output is correct
4 Correct 17 ms 70388 KB Output is correct
5 Correct 18 ms 70396 KB Output is correct
6 Correct 18 ms 70336 KB Output is correct
7 Correct 17 ms 70460 KB Output is correct
8 Correct 17 ms 70236 KB Output is correct
9 Correct 17 ms 70488 KB Output is correct
10 Correct 23 ms 72284 KB Output is correct
11 Correct 22 ms 72028 KB Output is correct
12 Correct 24 ms 72036 KB Output is correct
13 Correct 24 ms 72284 KB Output is correct
14 Correct 23 ms 72124 KB Output is correct
15 Correct 23 ms 72292 KB Output is correct
16 Correct 652 ms 190060 KB Output is correct
17 Correct 480 ms 196428 KB Output is correct
18 Correct 499 ms 194644 KB Output is correct
19 Correct 527 ms 193864 KB Output is correct
20 Correct 530 ms 193644 KB Output is correct
21 Correct 574 ms 194036 KB Output is correct
22 Correct 578 ms 191520 KB Output is correct
23 Correct 459 ms 196432 KB Output is correct
24 Correct 460 ms 193088 KB Output is correct
25 Correct 466 ms 192100 KB Output is correct
26 Correct 485 ms 192472 KB Output is correct
27 Correct 531 ms 192848 KB Output is correct
28 Correct 453 ms 199996 KB Output is correct
29 Correct 453 ms 199812 KB Output is correct
30 Correct 438 ms 199936 KB Output is correct
31 Correct 474 ms 199896 KB Output is correct
32 Correct 569 ms 191120 KB Output is correct
33 Correct 629 ms 194924 KB Output is correct
34 Correct 187 ms 114372 KB Output is correct
35 Correct 638 ms 197744 KB Output is correct
36 Correct 642 ms 194620 KB Output is correct
37 Correct 621 ms 196796 KB Output is correct
38 Correct 641 ms 195160 KB Output is correct
39 Correct 630 ms 201556 KB Output is correct
40 Correct 608 ms 203244 KB Output is correct
41 Correct 565 ms 195380 KB Output is correct
42 Correct 541 ms 192316 KB Output is correct
43 Correct 606 ms 201972 KB Output is correct
44 Correct 577 ms 196260 KB Output is correct
45 Correct 546 ms 200220 KB Output is correct
46 Correct 535 ms 200016 KB Output is correct
47 Correct 453 ms 200172 KB Output is correct
48 Correct 452 ms 200196 KB Output is correct
49 Correct 442 ms 199972 KB Output is correct
50 Correct 451 ms 199856 KB Output is correct
51 Correct 576 ms 202576 KB Output is correct
52 Correct 580 ms 202548 KB Output is correct