Submission #645382

#	Time	Username	Problem	Language	Result	Execution time	Memory
645382		x0r	Split the Attractions (IOI19_split)	C++17	40 / 100	94 ms	17612 KiB

split

#pragma GCC optimize ("O2")
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define fi first 
#define se second
#define pll pair < ll, ll >
#define pii pair < int, int >
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

const string NAME = "test";
const string NAME2 = "TEST";
const ld ESP = 1e-9;
const ll INF = 1e9 + 7;
const ll LINF = 1E18;
const ll nmax = 2e5;
const ll MOD = 1e9 + 7;
const ll base = 2309;

void fre() {
	string finp = NAME + ".inp";
	string fout = NAME + ".out";
	freopen(finp.c_str(), "r", stdin);
	freopen(fout.c_str(), "w", stdout);
}

int n, m, timer = 0, num[100003], low[100003], cnt_child[100003], root_b = 1, root_a = 0, a, b, c, res[100003], root;

int cnt_a = 0, cnt_b = 0;

bool give[100003], vs[100003];

vector < int > adj[100003];

void dfs(int u = 1, int e = 0) {
	num[u] = low[u] = ++ timer;
	cnt_child[u] = 1;
	for (auto v : adj[u]) {
		if (v == e) continue;
		if (!num[v]) {
			dfs(v, u);
			cnt_child[u] += cnt_child[v];
			low[u] = min(low[u], low[v]);
		}
		else low[u] = min(low[u], num[v]);
	}
}

void dfs_find(int u = 1) {
	vs[u] = 1;
	for (auto v : adj[u]) {
		if (num[v] < num[u] || vs[v]) continue;
		dfs_find(v);
	}
	if (root_a == 0) {
		bool th = (cnt_child[u] >= a);
		if (!th) return ;
		for (auto v : adj[u]) {
			if (num[v] < num[u]) continue ;
			if (cnt_child[v] >= a) return ;
		}
		if (n - cnt_child[u] < a) {
			th = false;
			int cnt = n - cnt_child[u];
			for (auto v : adj[u]) {
				if (num[v] < num[u]) continue;
				if (low[v] < num[u]) {
					cnt += cnt_child[v];
					cnt_child[u] -= cnt_child[v];
					give[v] = 1;
				}
				if (cnt >= a) {
					th = (cnt_child[u] >= a);
					break;
				}
			}
			if (!th)  
				for (auto v : adj[u]) {
					if (give[v]) cnt_child[u] += cnt_child[v];
					give[v] = false;
				}

		}
		if (th) root_a = root = u;
	}
}

void dfs_a(int u) {
	if (cnt_a == a) return ;
	cnt_a ++;
	res[u] = 2;
	for (auto v : adj[u]) {
		if (v == root_b || res[v] != 0) continue;
		if (root_a != root && give[v]) dfs_a(v);
		else {
			if (num[v] < num[u]) continue;
			dfs_a(v);
		}
	}
}

void dfs_b(int u) {
	if (cnt_b == b) return ;
	cnt_b ++;
	res[u] = 1;
	for (auto v : adj[u]) {
		if (v == root_a || res[v] != 0) continue;
		if (root_b != root && give[v]) dfs_b(v);
		else {
			if (num[v] < num[u]) continue;
			dfs_b(v);
		}
	}
}

vector<int> find_split(int _n, int x, int y, int z, vector<int> p, vector<int> q) {
    n = _n, m = p.size();
    vector < pii > temp;
	temp.push_back({x, 1});
	temp.push_back({y, 2});
	temp.push_back({z, 3});
	sort(temp.begin(), temp.end());
	a = temp[0].fi;
	b = temp[1].fi;
	c = temp[2].fi;
    for (int i = 0; i < m; i++) {
        int u = p[i], v = q[i];
        u++, v++;       
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
   	dfs();
	dfs_find();
	vector < int > ans(n, 0);
	if (root_a == 0) return ans;
	if (cnt_child[root_a] >= b) swap(root_a, root_b);
	dfs_a(root_a);
	dfs_b(root_b);
	for (int i = 1; i <= n; i++) ans[i - 1] = temp[2 - res[i]].se;
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'void fre()':
split.cpp:26:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  freopen(finp.c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:27:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |  freopen(fout.c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36