oj.uz

답안 #912601

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
912601 2024-01-19T16:22:05 Z Wansur Split the Attractions (IOI19_split) C++14
18 / 100
 92 ms 36476 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;

vector<pair<int,int>> del;
vector<pair<int,int>> add;
vector<int> ans;
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);
	}
}

void get(int v,int n,int a,int b,int c){
	vector<int> edg;
	for(int to:e[v]){
		edg.push_back(to);
	}
	int s=sz[v];
	for(int to:edg){
		if(s-sz[to]<a){
			break;
		}
		if(fup[to].f<tin[v]){
			s-=sz[to];
			e[v].erase(to);
			add.push_back({v,to});
			e[ver[fup[to].f]].insert(fup[to].s);
			del.push_back({ver[fup[to].f],fup[to].s});
		}
	}
	e[par[v]].erase(v);
	add.push_back({par[v],v});
	if(s>=a && n-s>=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(s>=b && n-s>=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];
		}
	}
}

std::vector<int> find_split(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]);
	}
	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]);
	}
	calc(0);
	int v=-1;
	vector<int> d;
	for(int i=0;i<n;i++){
		ans.push_back(0);
	}
	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){
			d.push_back(i);
		}
	}
	for(int v:d){
		del.clear();
		add.clear();
		get(v,n,a,b,c);
		if(ans[0]!=0)return ans;
		for(auto x:del){
			e[x.f].erase(x.s);
		}
		for(auto x:add){
			e[x.f].insert(x.s);
		}
	}
	return ans;
}

Compilation message

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

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16732 KB ok, correct split
2 Correct 5 ms 16836 KB ok, correct split
3 Correct 5 ms 16732 KB ok, correct split
4 Correct 4 ms 16732 KB ok, correct split
5 Correct 4 ms 16732 KB ok, correct split
6 Correct 4 ms 16732 KB ok, correct split
7 Correct 92 ms 36068 KB ok, correct split
8 Correct 73 ms 33816 KB ok, correct split
9 Correct 78 ms 32972 KB ok, correct split
10 Correct 68 ms 36476 KB ok, correct split
11 Correct 75 ms 36400 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16732 KB ok, correct split
2 Correct 3 ms 16732 KB ok, correct split
3 Correct 5 ms 16732 KB ok, correct split
4 Correct 80 ms 34004 KB ok, correct split
5 Correct 61 ms 29012 KB ok, correct split
6 Correct 69 ms 36436 KB ok, correct split
7 Correct 71 ms 33736 KB ok, correct split
8 Correct 89 ms 32168 KB ok, correct split
9 Correct 68 ms 28964 KB ok, correct split
10 Correct 71 ms 28884 KB ok, correct split
11 Correct 67 ms 28884 KB ok, correct split
12 Correct 68 ms 29316 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 16732 KB ok, correct split
2 Incorrect 66 ms 28668 KB invalid split: #1=40000, #2=20000, #3=40000
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16728 KB ok, correct split
2 Correct 4 ms 16856 KB ok, no valid answer
3 Correct 4 ms 16732 KB ok, correct split
4 Correct 3 ms 16732 KB ok, correct split
5 Correct 4 ms 16728 KB ok, correct split
6 Correct 4 ms 16732 KB ok, correct split
7 Correct 4 ms 16732 KB ok, correct split
8 Correct 4 ms 16860 KB ok, correct split
9 Correct 5 ms 17244 KB ok, correct split
10 Correct 6 ms 17192 KB ok, correct split
11 Correct 4 ms 16732 KB ok, correct split
12 Correct 6 ms 17240 KB ok, correct split
13 Correct 4 ms 16732 KB ok, correct split
14 Correct 4 ms 16996 KB ok, correct split
15 Correct 4 ms 16732 KB ok, correct split
16 Correct 4 ms 16848 KB ok, correct split
17 Correct 4 ms 16836 KB ok, correct split
18 Correct 4 ms 16732 KB ok, correct split
19 Correct 4 ms 16732 KB ok, correct split
20 Correct 4 ms 16988 KB ok, correct split
21 Correct 5 ms 17104 KB ok, correct split
22 Incorrect 6 ms 16988 KB invalid split: #1=850, #2=800, #3=850
23 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16732 KB ok, correct split
2 Correct 5 ms 16836 KB ok, correct split
3 Correct 5 ms 16732 KB ok, correct split
4 Correct 4 ms 16732 KB ok, correct split
5 Correct 4 ms 16732 KB ok, correct split
6 Correct 4 ms 16732 KB ok, correct split
7 Correct 92 ms 36068 KB ok, correct split
8 Correct 73 ms 33816 KB ok, correct split
9 Correct 78 ms 32972 KB ok, correct split
10 Correct 68 ms 36476 KB ok, correct split
11 Correct 75 ms 36400 KB ok, correct split
12 Correct 4 ms 16732 KB ok, correct split
13 Correct 3 ms 16732 KB ok, correct split
14 Correct 5 ms 16732 KB ok, correct split
15 Correct 80 ms 34004 KB ok, correct split
16 Correct 61 ms 29012 KB ok, correct split
17 Correct 69 ms 36436 KB ok, correct split
18 Correct 71 ms 33736 KB ok, correct split
19 Correct 89 ms 32168 KB ok, correct split
20 Correct 68 ms 28964 KB ok, correct split
21 Correct 71 ms 28884 KB ok, correct split
22 Correct 67 ms 28884 KB ok, correct split
23 Correct 68 ms 29316 KB ok, correct split
24 Correct 5 ms 16732 KB ok, correct split
25 Incorrect 66 ms 28668 KB invalid split: #1=40000, #2=20000, #3=40000
26 Halted 0 ms 0 KB -