oj.uz

Submission #209941

# Submission time Handle Problem Language Result Execution time Memory
209941 2020-03-16T03:27:43 Z Segtree Split the Attractions (IOI19_split) C++14
0 / 100
 2000 ms 14952 KB 
#include"split.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
#include<cassert>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef unordered_set<ll> uset;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=0;i<=n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("unroll-loops")
#pragma gcc target("avx2,see4")
ll N,A,B,C;
vector<ll> g[100010];
ll col[100010];
ll paint(ll x,ll from,ll rem,ll c){
	if(~col[x])return rem;
	if(rem<=0)return 0;
	col[x]=c;
	rem--;
	for(auto y:g[x])if(y!=from){
		rem=paint(y,x,rem,c);
	}
	return rem;
}
ll siz[100010],par[100010];
ll dfs(ll x,ll from){//部分木のサイズと親を求める
	siz[x]=1;
	par[x]=from;
	for(auto y:g[x])if(y!=from){
		siz[x]+=dfs(y,x);
	}
	return siz[x];
}
int finalcol[3];
vector<int> judge(ll root){//頂点rootを根としたdfs木で解く
	dfs(root,-1);
	rep(i,N)col[i]=-1;
	bool done=0;
	rep(i,N){
		ll x=siz[i],y=N-siz[i];
		if(A<=x&&B<=y){
			paint(i,par[i],A,0);
			paint(par[i],i,B,1);
			done=1;
			break;
		}
		if(A<=y&&B<=x){
			paint(i,par[i],B,1);
			paint(par[i],i,A,0);
			done=1;
			break;
		}
	}
	if(done==0){//
		vector<int> fans;
		rep(i,N)fans.push_back(0);
		return fans;
	}
	rep(i,N)if(col[i]==-1)col[i]=2;
	rep(i,N){
		col[i]=finalcol[col[i]];
	}
	vector<int> fans;
	rep(i,N)fans.push_back(col[i]);
	return fans;
}

vector<ll> f[3010];
bool vis[3010];
void make_dfstree(ll x,ll from){
	if(vis[x])return;
	vis[x]=1;
	if(from!=-1){
		g[x].push_back(from);
		g[from].push_back(x);
	}
	for(auto y:f[x]){
		make_dfstree(y,x);
	}
}
vector<int> find_split(int n,int a,int b,int c,vector<int> U,vector<int> V){
	N=n,A=a,B=b,C=c;
	int M=U.size();
	rep(i,M){
		f[U[i]].push_back(V[i]);
		f[V[i]].push_back(U[i]);
	}
	{//A<=B<=Cにする
		vector<P> v;
		v.push_back(make_pair(A,1));
		v.push_back(make_pair(B,2));
		v.push_back(make_pair(C,3));
		sort(all(v));
		rep(i,3)finalcol[i]=v[i].second;
		A=v[0].first;
		B=v[1].first;
		C=v[2].first;
	}
	vector<int> res;
	rep(i,N){
		rep(j,N){
			vis[j]=0;
			g[j].clear();
		}
		make_dfstree(i,-1);
		res=judge(i);
		if(res[0]!=0)return res;
	}
	return res;
}/*
int main(){
	int n,m,a,b,c;
	cin>>n>>m>>a>>b>>c;
	vector<int> U,V;
	rep(i,m){
		ll u,v;
		cin>>u>>v;
		U.push_back(u);
		V.push_back(v);
	}
	vector<int> fans=find_split(n,a,b,c,U,V);
	for(auto t:fans)cout<<t;
	cout<<endl;
}*/

Compilation message

split.cpp:18:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("O3")
 
split.cpp:19:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("unroll-loops")
 
split.cpp:20:0: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
 #pragma gcc target("avx2,see4")

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2808 KB ok, correct split
2 Correct 6 ms 2804 KB ok, correct split
3 Correct 6 ms 2680 KB ok, correct split
4 Correct 6 ms 2808 KB ok, correct split
5 Correct 9 ms 2680 KB ok, correct split
6 Correct 6 ms 2812 KB ok, correct split
7 Execution timed out 2057 ms 12268 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2808 KB ok, correct split
2 Correct 6 ms 2808 KB ok, correct split
3 Correct 6 ms 2808 KB ok, correct split
4 Execution timed out 2070 ms 14952 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2808 KB ok, correct split
2 Execution timed out 2024 ms 12904 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB ok, correct split
2 Correct 6 ms 2808 KB ok, no valid answer
3 Correct 6 ms 2808 KB ok, correct split
4 Correct 6 ms 2808 KB ok, correct split
5 Correct 6 ms 2808 KB ok, correct split
6 Correct 6 ms 2808 KB ok, correct split
7 Correct 6 ms 2680 KB ok, correct split
8 Correct 6 ms 2808 KB ok, correct split
9 Correct 9 ms 3192 KB ok, correct split
10 Correct 11 ms 3192 KB ok, correct split
11 Correct 6 ms 2808 KB ok, correct split
12 Correct 9 ms 3192 KB ok, correct split
13 Correct 6 ms 2680 KB ok, correct split
14 Correct 6 ms 2808 KB ok, correct split
15 Correct 6 ms 2808 KB ok, correct split
16 Correct 6 ms 2808 KB ok, correct split
17 Correct 6 ms 2680 KB ok, correct split
18 Correct 6 ms 2808 KB ok, correct split
19 Correct 6 ms 2808 KB ok, correct split
20 Correct 7 ms 2936 KB ok, correct split
21 Correct 8 ms 3064 KB ok, correct split
22 Correct 8 ms 3064 KB ok, correct split
23 Correct 8 ms 3064 KB ok, correct split
24 Correct 8 ms 3064 KB ok, correct split
25 Correct 8 ms 3192 KB ok, correct split
26 Incorrect 227 ms 3192 KB jury found a solution, contestant did not
27 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2808 KB ok, correct split
2 Correct 6 ms 2804 KB ok, correct split
3 Correct 6 ms 2680 KB ok, correct split
4 Correct 6 ms 2808 KB ok, correct split
5 Correct 9 ms 2680 KB ok, correct split
6 Correct 6 ms 2812 KB ok, correct split
7 Execution timed out 2057 ms 12268 KB Time limit exceeded
8 Halted 0 ms 0 KB -