Submission #628094

#	Time	Username	Problem	Language	Result	Execution time	Memory
628094		amunduzbaev	Thousands Islands (IOI22_islands)	C++17	12.35 / 100	1131 ms	961704 KiB

islands

#include "islands.h"
#include "bits/stdc++.h"
using namespace std;
#include <variant>

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
const int N = 2e5 + 5;
vector<int> edges[N];
int used[N], in[N];

variant<bool, vector<int>> find_journey(int n, int m, vector<int> u, vector<int> v) {
	map<ar<int, 2>, int> id;
	vector<int> r(m);
	for(int i=0;i<m;i++){
		edges[u[i]].push_back(i);
		if(id.count({v[i], u[i]})){
			int j = id[{v[i], u[i]}];
			r[j] = i, r[i] = j;
		}
		
		id[{u[i], v[i]}] = i;
	}
	
	if(edges[0].size() > 1){
		int a = edges[0][0], b = edges[0][1];
		return (vector<int>){a, r[a], b, r[b], r[a], a, r[b], b};
	}
	
	vector<int> par(n, -1), is(n);
	queue<int> q;
	for(int i=0;i<n;i++){
		if(edges[i].size() > 2){
			is[i] = 1;
			q.push(i);
		}
	}
	
	while(!q.empty()){
		int u = q.front(); q.pop();
		for(auto x : edges[u]){
			if(!is[v[x]]){
				is[v[x]] = 1;
				par[v[x]] = x ^ 1;
				q.push(v[x]);
			}
		}
	}
	
	if(!is[0]) return false;
	vector<int> t;
	int x = 0;
	while(~par[x]){
		t.push_back(par[x]);
		x = v[par[x]];
	}
	
	int a = edges[x][0], b = edges[x][1];
	if(a == (t.back() ^ 1)) a = edges[x][2];
	if(b == (t.back() ^ 1)) b = edges[x][2];
	assert(a != b && a != t.back() && b != t.back());
	vector<int> res = t, tmp = {a, a ^ 1, b, b ^ 1, a ^ 1, a, b ^ 1, b};
	res.insert(res.end(), tmp.begin(), tmp.end());
	reverse(t.begin(), t.end());
	res.insert(res.end(), t.begin(), t.end());
	assert(u[res[0]] == 0 && res[0] == res.back());
	
	vector<int> cnt(m);
	x = 0;
	for(int i=0;i<(int)res.size();i++){
		if(i) assert(res[i] != res[i-1]);
		assert(u[res[i]] == x);
		x = v[res[i]];
		swap(u[res[i]], v[res[i]]);
		cnt[res[i]] ^= 1;
		assert(0 <= res[i] && res[i] < m);
	}
	for(int i=0;i<m;i++){
		assert(!cnt[i]);
	}
	assert(!x);
	
	return res;
}

/*

5 8
0 1
1 0
1 2
2 1
2 3
3 2
2 4
4 2

*/

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7.35 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 45