oj.uz

Submission #912616

# Submission time Handle Problem Language Result Execution time Memory
912616 2024-01-19T16:32:58 Z Wansur Split the Attractions (IOI19_split) C++14
18 / 100
 135 ms 36996 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'

using namespace std;
typedef long long ll;
const int mx=2e5+12;

pair<int,int> fup[mx];
vector<int> g[mx];
set<int> e[mx];
int Ans[mx];
int par[mx];
int tin[mx];
int ver[mx];
int sz[mx];
int pos[]={1,2,3};
int timer;

void calc(int v){
	sz[v]=1;
	for(int to:g[v]){
		if(sz[to]>0)continue;
		calc(to);
		par[to]=v;
		e[v].insert(to);
		sz[v]+=sz[to];
	}
}

void dfs(int v,int p){
	tin[v]=fup[v].f=++timer;
	fup[v].s=v;
	ver[tin[v]]=v;
	for(int to:e[v]){
		if(to==p)continue;
		if(tin[to]>0){
			fup[v]=min(fup[v],{tin[to],v});
		}
		else{
			dfs(to,v);
			fup[v]=min(fup[v],fup[to]);
		}
	}
}

void get(int v,int p,int &cnt,int t){
	if(!cnt)return;
	Ans[v]=pos[t];
	cnt--;
	if(!cnt)return;
	for(int to:e[v]){
		get(to,v,cnt,t);
	}
}

std::vector<int> find(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q){
	for(int i=0;i<p.size();i++){
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}
	calc(0);
	int v=-1;
	for(int i=1;i<n;i++){
		if(sz[i]<a)continue;
		bool ok=1;
		for(int to:e[i]){
			if(sz[to]>=a)ok=0;
		}
		if(ok){
			v=i;
			break;
		}
	}
	vector<int> ans(n);
	if(v<0)return ans;
	bool bad=0;
	vector<int> edg;
	for(int to:e[v]){
		edg.push_back(to);
	}
	for(int to:edg){
		if(sz[v]-sz[to]<a){
			break;
		}
		if(fup[to].f<tin[v]){
			sz[v]-=sz[to];
			e[v].erase(to);
			e[ver[fup[to].f]].insert(fup[to].s);
		}
	}
	e[par[v]].erase(v);
	if(sz[v]>=a && n-sz[v]>=b){
		get(v,0,a,0);
		get(0,0,b,1);
		for(int i=0;i<n;i++){
			ans[i]=Ans[i];
			if(!ans[i])ans[i]=pos[2];
		}
	}
	else if(sz[v]>=b && n-sz[v]>=a){
		get(v,0,b,0);
		get(0,0,a,1);
		for(int i=0;i<n;i++){
			ans[i]=Ans[i];
			if(!ans[i])ans[i]=pos[2];
		}
	}
	return ans;
}

vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q){
	if(a>b){
		swap(a,b);
		swap(pos[0],pos[1]);
	}
	if(a>c){
		swap(a,c);
		swap(pos[0],pos[2]);
	}
	if(b>c){
		swap(b,c);
		swap(pos[1],pos[2]);
	}
	vector<int> ans(n);
	ans=find(n,a,b,c,p,q);
	if(ans[0]!=0)return ans;
	swap(a,b);
	swap(pos[0],pos[1]);
	for(int i=0;i<n;i++){
		g[i].clear();
		e[i].clear();
	}
	timer=0;
	ans=find(n,a,b,c,p,q);
	return ans;
	
}

Compilation message

split.cpp: In function 'std::vector<int> find(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:59:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~
split.cpp:78:7: warning: unused variable 'bad' [-Wunused-variable]
   78 |  bool bad=0;
      |       ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB ok, correct split
2 Correct 4 ms 16860 KB ok, correct split
3 Correct 4 ms 16732 KB ok, correct split
4 Correct 6 ms 16860 KB ok, correct split
5 Correct 5 ms 16728 KB ok, correct split
6 Correct 5 ms 16728 KB ok, correct split
7 Correct 110 ms 36576 KB ok, correct split
8 Correct 78 ms 34388 KB ok, correct split
9 Correct 84 ms 33820 KB ok, correct split
10 Correct 74 ms 36992 KB ok, correct split
11 Correct 87 ms 36996 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16732 KB ok, correct split
2 Correct 5 ms 16732 KB ok, correct split
3 Correct 5 ms 16732 KB ok, correct split
4 Correct 95 ms 34868 KB ok, correct split
5 Correct 99 ms 29624 KB ok, correct split
6 Correct 93 ms 36972 KB ok, correct split
7 Correct 122 ms 34132 KB ok, correct split
8 Correct 135 ms 33364 KB ok, correct split
9 Correct 93 ms 29264 KB ok, correct split
10 Correct 71 ms 29316 KB ok, correct split
11 Correct 80 ms 29132 KB ok, correct split
12 Correct 71 ms 29696 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16856 KB ok, correct split
2 Incorrect 79 ms 29268 KB invalid split: #1=40000, #2=20000, #3=40000
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16732 KB ok, correct split
2 Correct 5 ms 16728 KB ok, no valid answer
3 Correct 5 ms 16728 KB ok, correct split
4 Correct 8 ms 16880 KB ok, correct split
5 Correct 5 ms 16728 KB ok, correct split
6 Correct 5 ms 16732 KB ok, correct split
7 Correct 4 ms 16732 KB ok, correct split
8 Correct 4 ms 16728 KB ok, correct split
9 Correct 6 ms 17240 KB ok, correct split
10 Correct 5 ms 17240 KB ok, correct split
11 Correct 5 ms 16732 KB ok, correct split
12 Correct 8 ms 17244 KB ok, correct split
13 Correct 5 ms 16732 KB ok, correct split
14 Correct 5 ms 16728 KB ok, correct split
15 Correct 5 ms 16732 KB ok, correct split
16 Correct 5 ms 16888 KB ok, correct split
17 Correct 5 ms 16732 KB ok, correct split
18 Correct 5 ms 16728 KB ok, correct split
19 Correct 5 ms 16732 KB ok, correct split
20 Correct 6 ms 16988 KB ok, correct split
21 Correct 7 ms 16988 KB ok, correct split
22 Incorrect 7 ms 16988 KB invalid split: #1=850, #2=800, #3=850
23 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB ok, correct split
2 Correct 4 ms 16860 KB ok, correct split
3 Correct 4 ms 16732 KB ok, correct split
4 Correct 6 ms 16860 KB ok, correct split
5 Correct 5 ms 16728 KB ok, correct split
6 Correct 5 ms 16728 KB ok, correct split
7 Correct 110 ms 36576 KB ok, correct split
8 Correct 78 ms 34388 KB ok, correct split
9 Correct 84 ms 33820 KB ok, correct split
10 Correct 74 ms 36992 KB ok, correct split
11 Correct 87 ms 36996 KB ok, correct split
12 Correct 6 ms 16732 KB ok, correct split
13 Correct 5 ms 16732 KB ok, correct split
14 Correct 5 ms 16732 KB ok, correct split
15 Correct 95 ms 34868 KB ok, correct split
16 Correct 99 ms 29624 KB ok, correct split
17 Correct 93 ms 36972 KB ok, correct split
18 Correct 122 ms 34132 KB ok, correct split
19 Correct 135 ms 33364 KB ok, correct split
20 Correct 93 ms 29264 KB ok, correct split
21 Correct 71 ms 29316 KB ok, correct split
22 Correct 80 ms 29132 KB ok, correct split
23 Correct 71 ms 29696 KB ok, correct split
24 Correct 6 ms 16856 KB ok, correct split
25 Incorrect 79 ms 29268 KB invalid split: #1=40000, #2=20000, #3=40000
26 Halted 0 ms 0 KB -