Submission #840745

#	Time	Username	Problem	Language	Result	Execution time	Memory
840745		happypotato	Longest Trip (IOI23_longesttrip)	C++17	85 / 100	20 ms	648 KiB

longesttrip

#include "longesttrip.h"

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
// #define int long long // remove when necessary
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define ll long long
const int mxN = 256;
vector<int> adj[mxN];
vector<int> grp[mxN];
int conn[mxN][mxN];
int callcnt;
bool con(int x, int y) {
	// cerr << "CALLx " << x << ' ' << y << endl;
	if (x == y) return (conn[x][x] = 1);
	if (conn[x][y] != -1) return conn[x][y];
	callcnt++;
	return (conn[x][y] = conn[y][x] = are_connected({x}, {y}));
}
bool Con(vector<int> x, vector<int> y) {
	if (x.size() == 1 && y.size() == 1) {
		return con(x[0], y[0]);
	}
	// cerr << "CALL\n";
	// for (int &cur : x) cerr << cur << ' ';
	// cerr << endl;
	// for (int &cur : y) cerr << cur << ' ';
	// cerr << endl;
	callcnt++;
	return are_connected(x, y);
}
int n;
int dsupp[mxN];
vector<int> nxt[mxN];
bool vis[mxN];
void resetvis() {
	for (int i = 0; i < n; i++) vis[i] = false;
}
void reset() {
	callcnt = 0;
	for (int i = 0; i < n; i++) {
		adj[i].clear();
		grp[i].clear();
		for (int j = 0; j < n; j++) {
			conn[i][j] = -1;
		}
		dsupp[i] = i;
		nxt[i].clear();
		vis[i] = false;
	}
}
int DSUFind(int u) {
	if (dsupp[u] == u) return u;
	return (dsupp[u] = DSUFind(dsupp[u]));
}
void DSUMerge(int u, int v) {
	u = DSUFind(u); v = DSUFind(v);
	if (u != v) dsupp[v] = u;
}
vector<int> GetPath(int st) {
	resetvis();
	vector<int> res;
	while (true) {
		res.pb(st);
		vis[st] = true;
		bool found = false;
		for (int &v : nxt[st]) {
			if (!vis[v]) {
				st = v;
				found = true;
				break;
			}
		}
		if (!found) break;
	}
	return res;
}
vector<int> MakePath(vector<int> &v) {
	if (v.size() == 1) return {v[0]};
	if (v.size() == 2) {
		if (con(v[0], v[1])) return {v[0], v[1]};
		else return {v[0]};
	}
	if (v.size() == 3) {
		if (con(v[0], v[1]) && con(v[0], v[2])) return {v[1], v[0], v[2]};
		if (con(v[0], v[1]) && con(v[1], v[2])) return {v[0], v[1], v[2]};
		if (con(v[0], v[2]) && con(v[1], v[2])) return {v[0], v[2], v[1]};
		if (con(v[0], v[1])) return {v[0], v[1]};
		if (con(v[0], v[2])) return {v[0], v[2]};
		if (con(v[1], v[2])) return {v[1], v[2]};
		return {v[0]};
	}
	for (int i = 0; i < n; i++) {
		nxt[i].clear();
	}
	pair<pii, pii> cur = {{v[0], v[0]}, {v[1], v[1]}};
	for (int i = 2; i < (int)(v.size()); i++) {
		if (con(cur.ff.ff, cur.ss.ff)) {
			nxt[cur.ff.ff].pb(cur.ss.ff);
			nxt[cur.ss.ff].pb(cur.ff.ff);
			cur.ff.ff = cur.ss.ss;
			cur.ss = {v[i], v[i]};
		} else if (con(cur.ff.ff, v[i])) {
			nxt[cur.ff.ff].pb(v[i]);
			nxt[v[i]].pb(cur.ff.ff);
			cur.ff.ff = v[i];
		} else {
			conn[cur.ss.ff][v[i]] = conn[v[i]][cur.ss.ff] = 1;
			nxt[cur.ss.ff].pb(v[i]);
			nxt[v[i]].pb(cur.ss.ff);
			cur.ss.ff = v[i];
		}
	}
	vector<int> res[2];
	res[0] = GetPath(cur.ff.ff);
	res[1] = GetPath(cur.ss.ff);
	if (!Con(res[0], res[1])) {
		return (res[0].size() >= res[1].size() ? res[0] : res[1]);
	}
	int st;
	if (con(cur.ff.ff, cur.ss.ff)) {
		nxt[cur.ff.ff].pb(cur.ss.ff);
		nxt[cur.ss.ff].pb(cur.ff.ff);
		st = cur.ff.ss;
	} else if (con(cur.ff.ff, cur.ss.ss)) {
		nxt[cur.ff.ff].pb(cur.ss.ss);
		nxt[cur.ss.ss].pb(cur.ff.ff);
		st = cur.ff.ss;
	} else if (con(cur.ff.ss, cur.ss.ff)) {
		nxt[cur.ff.ss].pb(cur.ss.ff);
		nxt[cur.ss.ff].pb(cur.ff.ss);
		st = cur.ff.ff;
	} else if (con(cur.ff.ss, cur.ss.ss)) {
		nxt[cur.ff.ss].pb(cur.ss.ss);
		nxt[cur.ss.ss].pb(cur.ff.ss);
		st = cur.ff.ff;
	} else {
		vector<int> take[2];
		take[0] = res[0];
		take[1] = res[1];

		// cerr << "res0: ";
		// for (int &x : res[0]) cerr << x << ' ';
		// cerr << endl;
		// cerr << "res1: ";
		// for (int &x : res[1]) cerr << x << ' ';
		// cerr << endl;

		vector<int> split[2];
		while (take[0].size() >= 2) {
			split[0].clear();
			split[1].clear();
			int cut = (int)(take[0].size()) / 2;
			for (int i = 0; i < cut; i++) split[0].pb(take[0][i]);
			for (int i = cut; i < (int)(take[0].size()); i++) split[1].pb(take[0][i]);
			if (Con(split[0], take[1])) take[0] = split[0];
			else take[0] = split[1];
		}
		while (take[1].size() >= 2) {
			split[0].clear();
			split[1].clear();
			int cut = (int)(take[1].size()) / 2;
			for (int i = 0; i < cut; i++) split[0].pb(take[1][i]);
			for (int i = cut; i < (int)(take[1].size()); i++) split[1].pb(take[1][i]);
			if (Con(take[0], split[0])) take[1] = split[0];
			else take[1] = split[1];
		}

		bool found = false;
		for (int i = 0; i < (int)(res[0].size()); i++) {
			if (res[0][i] != take[0][0]) continue;
			for (int j = 0; j < (int)(res[1].size()); j++) {
				if (res[1][j] != take[1][0]) continue;
				if (true) {
					// cerr << "FOUND " << res[0][i] << ' ' << res[1][j] << endl;
					nxt[res[0][i]].pb(res[1][j]);
					nxt[res[1][j]].pb(res[0][i]);
 
					if (res[0].size() >= 3) {
						nxt[cur.ff.ff].pb(cur.ff.ss);
						nxt[cur.ff.ss].pb(cur.ff.ff);
						// cerr << "RES0 ";
						// for (int &x : res[0]) cerr << x << ' ';
						// cerr << endl;
						st = (i == 0 ? res[0].back() : res[0][i - 1]);
						// cerr << "ST " << st << endl;
						vector<int>::iterator it;
						for (it = nxt[st].begin(); it != nxt[st].end(); ++it) {
							if (*it == res[0][i]) {
								nxt[st].erase(it);
								break;
							}
						}
						for (it = nxt[res[0][i]].begin(); it != nxt[res[0][i]].end(); ++it) {
							if (*it == st) {
								nxt[res[0][i]].erase(it);
								break;
							}
						}
					} else {
						st = (res[0].size() == 2 ? res[0][i ^ 1] : res[0][i]);
					}
 
					if (res[1].size() >= 3) {
						nxt[cur.ss.ff].pb(cur.ss.ss);
						nxt[cur.ss.ss].pb(cur.ss.ff);
						int tar = (j == 0 ? res[1].back() : res[1][j + 1]);
						vector<int>::iterator it;
						for (it = nxt[tar].begin(); it != nxt[tar].end(); ++it) {
							if (*it == res[1][j]) {
								nxt[tar].erase(it);
								break;
							}
						}
						for (it = nxt[res[1][j]].begin(); it != nxt[res[1][j]].end(); ++it) {
							if (*it == tar) {
								nxt[res[1][j]].erase(it);
								break;
							}
						}
					}
 
					found = true;
					break;
				}
			}
			if (found) break;
		}

		// cerr << "END\n";
	}

	// cerr << "find path for: ";
	// for (int &x : v) cerr << x << ' ';
	// cerr << endl;
	
	vector<int> fin = GetPath(st);

	// cerr << "st: " << st << endl;
	// cerr << "result: ";
	// for (int &x : res) cerr << x << ' ';
	// cerr << endl;

	return fin;
}
vector<int> longest_trip(int N, int D)
{
	n = N;
	reset();

	// queue<int> q;
	// for (int i = 0; i < n; i++) {
	// 	grp[i].clear();
	// 	grp[i].pb(i);
	// 	q.push(i);
	// }
	// while (q.size() >= 3) {
	// 	int a = q.front(); q.pop();
	// 	int b = q.front(); q.pop();
	// 	int c = q.front(); q.pop();
	// 	// cerr << a << ' ' << b << ' ' << c << endl;
	// 	if (Con(grp[a], grp[b])) {
	// 		DSUMerge(a, b);
	// 		for (int &x : grp[b]) grp[a].pb(x);
	// 		grp[b].clear();
	// 		q.push(a);
	// 		q.push(c);
	// 	} else if (Con(grp[a], grp[c])) {
	// 		DSUMerge(a, c);
	// 		for (int &x : grp[c]) grp[a].pb(x);
	// 		grp[c].clear();
	// 		q.push(a);
	// 		q.push(b);
	// 	} else {
	// 		DSUMerge(b, c);
	// 		for (int &x : grp[c]) grp[b].pb(x);
	// 		grp[c].clear();
	// 		q.push(a);
	// 		q.push(b);
	// 	}
	// }
	// int fina = q.front(); q.pop();
	// int finb = q.front(); q.pop();
	// if (Con(grp[fina], grp[finb])) {
	// 	DSUMerge(fina, finb);
	// 	for (int &x : grp[finb]) grp[fina].pb(x);
	// 	grp[finb].clear();
	// }

	// // cerr << "CALLCNT " << callcnt << endl;

	// vector<int> best = {};
	// for (int i = 0; i < n; i++) {
	// 	if (grp[i].empty()) continue;
	// 	vector<int> res = MakePath(grp[i]);
	// 	if (res.size() > best.size()) {
	// 		best = res;
	// 	}
	// }
	// return best;

	vector<int> res(n);
	for (int i = 0; i < n; i++) res[i] = i;
	return MakePath(res);
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> MakePath(std::vector<int>&)':
longesttrip.cpp:241:30: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
  241 |  vector<int> fin = GetPath(st);
      |                              ^

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 45 / 60