Submission #1160768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160768		duckindog	Simurgh (IOI17_simurgh)	C++20	51 / 100	277 ms	3752 KiB

simurgh

#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
#include "simurgh.h"
#endif

#ifdef LOCAL
static int MAXQ = 30000;

static int n, m, q = 0;
static vector<int> u, v;
static vector<bool> goal;

static void wrong_answer() {
	printf("NO\n");
	exit(0);
}

static bool is_valid(const vector<int>& r) {
	if(int(r.size()) != n - 1)
		return false;

	for(int i = 0; i < n - 1; i++)
		if (r[i] < 0 || r[i] >= m)
			return false;

	return true;
}

static int _count_common_roads_internal(const vector<int>& r) {
	if(!is_valid(r))
		wrong_answer();

	int common = 0;
	for(int i = 0; i < n - 1; i++) {
		bool is_common = goal[r[i]];
		if (is_common)
			common++;
	}

	return common;	
}

int count_common_roads(const vector<int>& r) {
	q++;
	if(q > MAXQ)
		wrong_answer();

	return _count_common_roads_internal(r);
}
#endif

const int N = 500 + 10;
vector<pair<int, int>> edges;
vector<pair<int, int>> ad[N];

struct DSU { 
	int id[N * N];

	DSU() { memset(id, -1, sizeof id); }
	void clear() { memset(id, -1, sizeof id); }

	int root(int u) { return id[u] < 0 ? u : id[u] = root(id[u]); }
	void add(int u, int v) { 
		u = root(u); v = root(v);
		if (id[u] > id[v]) swap(u, v);
		if (u == v) return;
		id[u] += id[v];
		id[v] = u;
	}

	bool isCon(int u, int v) { return root(u) == root(v); }
} A, B;


vector<int> paths;
bool findPath(int u, int p, int t) { 
	if (u == t) return true;

	bool ret = false;
	for (const auto& [v, idx] : ad[u]) { 
		if (v == p) continue;
		if (findPath(v, u, t)) { 
			ret = true;
			paths.push_back(idx);
		}
	}
	return ret;
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	for (int i = 0; i < n - 1; ++i) {
		edges.push_back({u[i], v[i]});
	}

	const int m = u.size(), NO = m, YES = m + 1;

	vector<int> curList;
	for (int i = 0; i < m; ++i) { 
		if (B.isCon(u[i], v[i])) continue;
		B.add(u[i], v[i]);

		ad[u[i]].push_back({v[i], i});
		ad[v[i]].push_back({u[i], i});

		curList.push_back(i);
	}
	
	int cnt = count_common_roads(curList);
	{ // greedy shit
		if (!cnt) { 
			for (const auto& idx : curList) A.add(idx, NO);
		}
		if (cnt == n - 1) return curList;
	}

	for (int i = 0; i < m; ++i) { 
		if (A.isCon(i, NO) || A.isCon(i, YES)) continue;
		if (count(curList.begin(), curList.end(), i)) continue;

		paths.clear();
		for (int j = 0; j < n; ++j) ad[j].clear();
		for (const auto& idx : curList) { 
			ad[u[idx]].push_back({v[idx], idx});
			ad[v[idx]].push_back({u[idx], idx});	
		}

		findPath(u[i], -1, v[i]);
		shuffle(paths.begin(), paths.end(), mt19937_64(149973));
		for (const auto& idx : paths) { 
			if (A.isCon(i, idx)) continue;
			if ((A.isCon(i, YES) || A.isCon(i, NO)) && 
					(A.isCon(idx, YES) || A.isCon(idx, NO))) continue;

			vector<int> nList = curList;
			nList.erase(find(nList.begin(), nList.end(), idx));
			nList.push_back(i);

			int nCnt = count_common_roads(nList);

			if (nCnt < cnt) A.add(i, NO), A.add(idx, YES);
			if (nCnt == cnt) A.add(i, idx);
			if (nCnt > cnt) A.add(i, YES), A.add(idx, NO);
		}

		if (A.isCon(i, YES)) { 
			B.clear();

			curList.clear();
			for (int j = 0; j < m; ++j) { 
				if (A.isCon(j, YES)) { 
					curList.push_back(j);
					B.add(u[j], v[j]);
				}
			}
			for (int j = 0; j < m; ++j) { 
				if (!B.isCon(u[j], v[j])) { 
					curList.push_back(j);
					B.add(u[j], v[j]);
				}
			}
			cnt += 1;
		}

		if (cnt == n - 1) return curList;
	}
	assert(false);
}

#ifdef LOCAL
int main() {
	assert(2 == scanf("%d %d", &n, &m));

	u.resize(m);
	v.resize(m);

	for(int i = 0; i < m; i++)
		assert(2 == scanf("%d %d", &u[i], &v[i]));

	goal.resize(m, false);

	for(int i = 0; i < n - 1; i++) {
		int id;
		assert(1 == scanf("%d", &id));
		goal[id] = true;
	}

	vector<int> res = find_roads(n, u, v);
	cerr << q << "\n";	
	if(_count_common_roads_internal(res) != n - 1)
		wrong_answer();
	printf("YES\n");

	return 0;
}
#endif

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30