oj.uz

Submission #893423

# Submission time Handle Problem Language Result Execution time Memory
893423 2023-12-27T04:43:43 Z Jawad_Akbar_JJ Split the Attractions (IOI19_split) C++17
11 / 100
 107 ms 58920 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;
	if (!found){
		for (int i=1;i<=n;i++)
			col.push_back(0);
		return col;
	}
	for (int i=1;i<=n;i++){
		if (color[i]==0)
			col.push_back(v[2][1]);
		else
			col.push_back(color[i]);
	}
	return col;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4188 KB ok, correct split
2 Correct 2 ms 4444 KB ok, correct split
3 Correct 1 ms 4184 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 2 ms 4188 KB ok, correct split
2 Correct 2 ms 4188 KB ok, correct split
3 Correct 1 ms 4188 KB ok, correct split
4 Correct 74 ms 21624 KB ok, correct split
5 Correct 40 ms 9688 KB ok, correct split
6 Correct 107 ms 58920 KB ok, correct split
7 Correct 73 ms 28500 KB ok, correct split
8 Correct 64 ms 11984 KB ok, correct split
9 Correct 42 ms 9972 KB ok, correct split
10 Correct 46 ms 11732 KB ok, correct split
11 Correct 49 ms 14028 KB ok, correct split
12 Correct 52 ms 14220 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB ok, correct split
2 Incorrect 48 ms 9684 KB secret mismatch
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

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

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4188 KB ok, correct split
2 Correct 2 ms 4444 KB ok, correct split
3 Correct 1 ms 4184 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 -