oj.uz

Submission #954739

# Submission time Handle Problem Language Result Execution time Memory
954739 2024-03-28T13:09:08 Z waldi Split the Attractions (IOI19_split) C++17
22 / 100
 162 ms 41592 KB 
#include "split.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;

struct fnu{
	vector<int> r;
	fnu(int n){
		r.resize(n);
		REP(i, n) r[i] = i;
	}
	int f(int x){
		if(r[x] != x) r[x] = f(r[x]);
		return r[x];
	}
	void u(int a, int b){
		a = f(a), b = f(b), r[a] = b;
	}
};

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
	vector<int> kolor = {1, 2, 3};
	if(b > c) swap(b, c), swap(kolor[1], kolor[2]);
	if(a > b) swap(a, b), swap(kolor[0], kolor[1]);
	if(b > c) swap(b, c), swap(kolor[1], kolor[2]);
	
	int m = ssize(p);
	vector<vector<pii>> g(n);
	REP(i, m){
		int a = p[i], b = q[i];
		g[a].emplace_back(b, i);
		g[b].emplace_back(a, i);
	}
	
	fnu janusz(m);
	vector<int> odw(n, 0), gl(n, 0), low(n, -1);
	function<void(int, int)> dfs = [&](int w, int id_o){
		odw[w] = 1;
		low[w] = gl[w];
		for(pii i : g[w]) if(i.se != id_o){
			if(!odw[i.fi]){
				gl[i.fi] = gl[w]+1;
				dfs(i.fi, i.se);
				if(low[i.fi] < gl[w]) janusz.u(id_o, i.se);
				low[w] = min(low[w], low[i.fi]);
			}
			else if(gl[i.fi] < gl[w]){
				janusz.u(id_o, i.se);
				low[w] = min(low[w], gl[i.fi]);
			}
		}
	};
	dfs(0, -1);
	
	int it = 0;
	vector<int> skal(m, -1);
	vector<int> spojna(m);
	REP(i, m){
		int t = janusz.f(i);
		if(skal[t] < 0) skal[t] = it++;
		spojna[i] = skal[t];
	}
	
	//~ REP(i, m) printf("%d: %d\n", i, spojna[i]);
	
	vector<vector<int>> sklad(it);
	
	vector<vector<int>> drz(it);
	vector<int> waga(it, 0);
	
	REP(w, n){
		set<int> sas;
		for(pii i : g[w]) sas.emplace(spojna[i.se]);
		if(ssize(sas) == 1){
			sklad[*sas.begin()].emplace_back(w);
			++waga[*sas.begin()];
			continue;
		}
		sklad.push_back({w});
		waga.emplace_back(1);
		drz.emplace_back();
		for(int x : sas){
			drz[it].emplace_back(x);
			drz[x].emplace_back(it);
		}
		++it;
	}
	
	//~ printf("it: %d\n", it);
	//~ REP(i, it){
		//~ printf("%d: ", i);
		//~ for(int x : sklad[i]) printf("%d ", x);
		//~ printf("\n");
	//~ }
	
	//~ printf("drz:\n");
	//~ REP(i, it){
		//~ printf("%d: ", i);
		//~ for(int x : drz[i]) printf("%d ", x);
		//~ printf("\n");
	//~ }
	
	vector pdd = waga;
	vector<int> oj(it);
	function<void(int, int)> dfs_pdd = [&](int w, int o){
		oj[w] = o;
		for(int i : drz[w]) if(i != o) dfs_pdd(i, w), pdd[w] += pdd[i];
	};
	dfs_pdd(0, -1);
	
	REP(xd, 2){
		int ktory = -1;
		REP(i, it) if(pdd[i] >= a){
			if(n-pdd[i] >= b){
				ktory = i;
				break;
			}
		}
		if(ktory >= 0){
			vector czy(n, 0);
			function<void(int)> dfs_odzyskaj = [&](int w){
				for(int x : sklad[w]) czy[x] = 1;
				for(int i : drz[w]) if(i != oj[w]) dfs_odzyskaj(i);
			};
			dfs_odzyskaj(ktory);
			
			//~ REP(i, n) if(czy[i]) printf("czy: %d\n", i);
			
			vector ret(n, kolor[2]);
			function<void(int)> dfs_pomaluj_a = [&](int w){
				//~ printf("a: %d\n", w);
				if(!a) return;
				ret[w] = kolor[0], --a;
				for(auto [i, jajco] : g[w]) if(czy[i] && ret[i] == kolor[2]) dfs_pomaluj_a(i);
			};
			function<void(int)> dfs_pomaluj_b = [&](int w){
				//~ printf("b: %d\n", w);
				if(!b) return;
				ret[w] = kolor[1], --b;
				for(auto [i, jajco] : g[w]) if(!czy[i] && ret[i] == kolor[2]) dfs_pomaluj_b(i);
			};
			REP(i, n) if(czy[i]){dfs_pomaluj_a(i); break;}
			REP(i, n) if(!czy[i]){dfs_pomaluj_b(i); break;}
			return ret;
		}
		swap(a, b);
		swap(kolor[0], kolor[1]);
	}
	return vector(n, 0);
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok, correct split
2 Incorrect 0 ms 600 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Incorrect 0 ms 348 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok, correct split
2 Correct 135 ms 29820 KB ok, correct split
3 Correct 37 ms 11876 KB ok, correct split
4 Correct 1 ms 348 KB ok, correct split
5 Correct 151 ms 40732 KB ok, correct split
6 Correct 151 ms 38328 KB ok, correct split
7 Correct 134 ms 41592 KB ok, correct split
8 Correct 152 ms 41328 KB ok, correct split
9 Correct 162 ms 40312 KB ok, correct split
10 Correct 26 ms 9656 KB ok, no valid answer
11 Correct 42 ms 14908 KB ok, no valid answer
12 Correct 84 ms 27120 KB ok, no valid answer
13 Correct 96 ms 28356 KB ok, no valid answer
14 Correct 105 ms 29816 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok, correct split
2 Correct 0 ms 348 KB ok, no valid answer
3 Incorrect 0 ms 348 KB jury found a solution, contestant did not
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok, correct split
2 Incorrect 0 ms 600 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -