oj.uz

Submission #893415

# Submission time Handle Problem Language Result Execution time Memory
893415 2023-12-27T04:36:38 Z Jawad_Akbar_JJ Split the Attractions (IOI19_split) C++17
11 / 100
 101 ms 59060 KB 
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include "split.h"
#include <algorithm>

using namespace std;
const int N = 1e5 + 10;

vector<vector<int>> v;
vector<int> nei[N];
int A,B;
int mn[N];
int sz[N];
int hei[N];
bool seen[N];
int color[N];
bool found = false;
int K;

void dfs_color(int u,int c){
	if (seen[u])
		return;
	if (K<=0)
		return;
	color[u] = c;
	seen[u] = true;
	K--;
	for (int i : nei[u]){
		if (seen[i])
			continue;
		dfs_color(i,c);
	}
}

void dfs(int u,int h = 1){
	sz[u] = 1;
	hei[u] = h++;
	seen[u] = true;
	mn[u] = hei[u];
	for (int i : nei[u]){
		if (seen[i]){
			mn[u] = min(mn[u],hei[i]);
			continue;
		}
		dfs(i,h);
		sz[u] += sz[i];
		if (mn[i])
			mn[u] = min(mn[u],mn[i]);
	}
}

// #################################### reset seen
bool called = false;
void call(int u,set<int> s,int c,int Sz){
	if (called)
		return;
	called = true;
	memset(seen,false,sizeof seen);
	seen[u] = true;
	color[u] = c;
	Sz--;
	K = Sz;
	for (int i : s){
		int aa = K;
		dfs_color(i,c);
		cout<<u<<" "<<sz[i]<<" "<<aa - K<<endl;
	}
}

void dfs2(int u){
	seen[u] = true; 
	int p1 = sz[u];
	int p2 = sz[1] - sz[u];

	set<int> s;

	for (int  i : nei[u])
		if (!seen[i]){
			s.insert(i);
			dfs2(i);
		}

	if (p1>=A and p2>=B){
		call(u,s,v[0][1],A);
		K = B;
		dfs_color(1,v[1][1]);
		found = true;
		return;
	}
	else if (p1>=B and p2>=A){
		call(u,s,v[1][1],B);
		K = A;
		dfs_color(1,v[0][1]);
		found = true;
		return;
	}

	for (int i : nei[u]){
		if (seen[i])
			continue;

		if (found)
			return;
		
		if (mn[i]>=hei[u])
			continue;
		
		if (p1 - sz[i] >= A){
			s.erase(i);
			p1 -= sz[i];
			p2 += sz[i];
		}
		if (p1>=A and p2>=B){
			call(u,s,v[0][1],A);
			K = B;
			dfs_color(1,v[1][1]);
			found = true;
			return;
		}
		else if (p1>=B and p2>=A){
			call(u,s,v[1][1],B);
			K = A;
			dfs_color(1,v[0][1]);
			found = true;
			return;
		}
	}
}

vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q){
	int m = p.size();

	for (int i=0;i<m;i++){
		p[i]++;
		q[i]++;
		nei[p[i]].push_back(q[i]);
		nei[q[i]].push_back(p[i]);
	}
	v.push_back({a,1});
	v.push_back({b,2});
	v.push_back({c,3});

	sort(begin(v),end(v));

	A = v[0][0];
	B = v[1][0];

	dfs(1,1);

	memset(seen,false,sizeof seen);

	dfs2(1);

	vector<int> col(n);
	if (!found)
		return col;
	for (int i=1;i<=n;i++){
		if (color[i]==0)
			col[i-1] = v[2][1];
		else
			col[i-1] = color[i];
	}
	return col;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB ok, correct split
2 Correct 1 ms 4188 KB ok, correct split
3 Correct 1 ms 4188 KB ok, correct split
4 Correct 1 ms 4188 KB ok, correct split
5 Correct 1 ms 4188 KB ok, correct split
6 Incorrect 2 ms 4188 KB secret mismatch
7 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4188 KB ok, correct split
2 Correct 1 ms 4188 KB ok, correct split
3 Correct 1 ms 4188 KB ok, correct split
4 Correct 76 ms 21772 KB ok, correct split
5 Correct 38 ms 9428 KB ok, correct split
6 Correct 101 ms 59060 KB ok, correct split
7 Correct 90 ms 28500 KB ok, correct split
8 Correct 62 ms 11856 KB ok, correct split
9 Correct 39 ms 9812 KB ok, correct split
10 Correct 43 ms 11724 KB ok, correct split
11 Correct 46 ms 13984 KB ok, correct split
12 Correct 46 ms 14036 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB ok, correct split
2 Incorrect 46 ms 9556 KB secret mismatch
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4184 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB ok, correct split
2 Correct 1 ms 4188 KB ok, correct split
3 Correct 1 ms 4188 KB ok, correct split
4 Correct 1 ms 4188 KB ok, correct split
5 Correct 1 ms 4188 KB ok, correct split
6 Incorrect 2 ms 4188 KB secret mismatch
7 Halted 0 ms 0 KB -