Submission #152656

#	Time	Username	Problem	Language	Result	Execution time	Memory
152656		qkxwsm	Simurgh (IOI17_simurgh)	C++14	30 / 100	283 ms	6748 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 513
#define INF 1000000007
#define MOD 1000000931

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, Q, M, T, K;
int eid[MAXN][MAXN];
int res[MAXN][MAXN];
ll pw[MAXN * MAXN], PW[MAXN * MAXN];
vi edge[MAXN];
vi edge1[MAXN];
int parent[MAXN];
bitset<MAXN> seen;
map<ll, int> mp;
vi ans;

struct dsu
{
	int dsu[MAXN];
	void init()
	{
		FOR(i, 0, N) dsu[i] = i;
	}
	int get(int u)
	{
		return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
	}
	bool merge(int u, int v)
	{
		u = get(u); v = get(v);
		if (u == v) return false;
		dsu[v] = u; return true;
	}
};
void dfs1(int u, int p)
{
	for (int v : edge1[u])
	{
		if (v == p) continue;
		parent[v] = u;
		dfs1(v, u);
	}
}
vi getpath(int u, int v)
{
	vi pu, pv;
	while(u != 0)
	{
		pu.PB(u);
		u = parent[u];
	}
	pu.PB(0);
	while(v != 0)
	{
		pv.PB(v);
		v = parent[v];
	}
	pv.PB(0);
	int r = -1;
	while(!pu.empty() && !pv.empty() && pu.back() == pv.back())
	{
		r = pu.back();
		pu.pop_back(); pv.pop_back();
	}
	pu.PB(r);
	reverse(ALL(pv));
	pu.insert(pu.end(), ALL(pv));
	return pu; //gets the path from pu to pv in O(N) time.
}
dsu D;

int ask(vi x)
{
	// cerr << "ASK\n";
	// for (int a : x)
	// {
	// 	cerr << a << ' ';
	// }
	// cerr << endl;
	ll sum = 0, SUM = 0;
	for (int y : x)
	{
		sum += pw[y]; if (sum >= INF) sum -= INF;
		SUM += PW[y]; if (SUM >= MOD) SUM -= MOD;
	}
	ll key = sum * MOD + SUM;
	auto it = mp.find(key);
	if (it != mp.end()) return it -> se;
	int res = count_common_roads(x);
	mp[key] = res;
	// cerr << "RECEIVE " << res << endl;
	return res;
}

vi find_roads(int n, vi U, vi V)
{
	N = n; M = SZ(U);
	pw[0] = 1; PW[0] = 1;
	FOR(i, 0, M)
	{
		if (U[i] > V[i]) swap(U[i], V[i]);
		edge[U[i]].PB(V[i]);
		edge[V[i]].PB(U[i]);
		eid[U[i]][V[i]] = i;
		eid[V[i]][U[i]] = i;
		res[U[i]][V[i]] = -1;
		res[V[i]][U[i]] = -1;
		pw[i + 1] = pw[i] + pw[i]; if (pw[i + 1] >= INF) pw[i + 1] -= INF;
		PW[i + 1] = PW[i] + PW[i]; if (PW[i + 1] >= MOD) PW[i + 1] -= MOD;
	}
	D.init();
	// cerr << "SPANNING TREE\n";
	FOR(u, 0, N)
	{
		for (int v : edge[u])
		{
			if (v < u) continue;
			if (D.merge(u, v))
			{
				// cerr << u << ' ' << v << endl;
				edge1[u].PB(v);
				edge1[v].PB(u);
			}
		}
	}
	dfs1(0, N);
	parent[0] = N;
	// cerr << "SOLVE\n";
	//ok now the idea is: for all edges, find a cycle.
	//if the cycle has all new edges, you solve the cycle in O(size)
	//else, you can just solve the edge using the known edge.
	FOR(u, 0, N)
	{
		for (int v : edge[u])
		{
			if (v < u) continue;
			if (res[u][v] != -1) continue;
			if (u == parent[v] || v == parent[u]) continue;
			// cerr << "NEW ROUND\n";
			//ok solve u, v.
			//find any cycle that (u, v) is part of.
			vi cyc = getpath(u, v); cyc.PB(u);
			// cerr << "getpath " << u << ' ' << v << endl;
			// for (int x : cyc)
			// {
			// 	cerr << x << ' ';
			// }
			// cerr << endl;
			vi qry; int mn = 0;
			FOR(i, 0, SZ(cyc) - 1)
			{
				qry.PB(eid[cyc[i]][cyc[i + 1]]);
			}
			int solved = -1;
			FOR(i, 0, SZ(cyc) - 2)
			{
				int w = cyc[i], x = cyc[i + 1];
				if (res[w][x] != -1)
				{
					// cerr << "SOLVED " << w << ' ' << x << endl;
					// w..x is solved.
					solved = i;
					break;
				}
			}
			//complete the tree
			seen.reset();
			FOR(i, 0, SZ(cyc) - 2)
			{
				int w = cyc[i], x = cyc[i + 1];
				if (x == parent[w]) seen[w] = true;
				else seen[x] = true;
			}
			FOR(i, 1, N)
			{
				if (!seen[i])
				{
					// cerr << "NOTVIS " << i << endl;
					qry.PB(eid[i][parent[i]]);
				}
			}
			// cerr << "QRY\n";
			// for (int x : qry)
			// {
			// 	cerr << x << ' ';
			// }
			// cerr << endl;
			// if (solved == -1)
			// {
				vi dp(SZ(cyc) - 1);
				assert(SZ(qry) == N);
				FOR(i, 0, SZ(cyc) - 1)
				{
					int x = qry[i];
					swap(qry[i], qry[N - 1]);
					qry.pop_back();
					dp[i] = ask(qry);
					ckmax(mn, dp[i]);
					qry.PB(x);
					swap(qry[i], qry[N - 1]);
				}
				// cerr << "mn = " << mn << endl;
				FOR(i, 0, SZ(cyc) - 1)
				{
					int w = cyc[i], x = cyc[i + 1];
					res[w][x] = (dp[i] == mn ? 0 : 1);
					// cerr << w << ' ' << x << ' ' << dp[i] << ' ' << res[w][x] << endl;
					res[x][w] = res[w][x];
				}
			// }
			// else
			// {
			// 	//i...i+1
			// 	assert(SZ(qry) == N);
			// 	// cerr << "HELP " << u << ' ' << v << endl;
			// 	int x = eid[v][u];
			// 	qry.erase(qry.begin() + SZ(cyc) - 2);
			// 	int cur = ask(qry);
			// 	qry[solved] = x;
			// 	mn = ask(qry);
			// 	res[u][v] = (mn - cur) + res[cyc[solved]][cyc[solved + 1]];
			// 	res[v][u] = res[u][v];
			// }
			//you can do that with a spanning tree!
		}
	}
	D.init();
	FOR(u, 0, N)
	{
		for (int v : edge[u])
		{
			if (v < u) continue;
			if (res[u][v] == -1)
			{
				res[u][v] = 1;
			}
			if (res[u][v] == 1)
			{
				// cerr << "WORKED " << u << ' ' << v << endl;
				ans.PB(eid[u][v]);
				D.merge(u, v);
			}
		}
	}
	FOR(u, 0, N)
	{
		for (int v : edge[u])
		{
			if (v < u) continue;
			if (res[u][v] == -1)
			{
				res[u][v] = 1;
			}
		}
	}
	// cerr << "ANS\n";
	// for (int x : ans)
	// {
	// 	cerr << x << ' ';
	// }
	// cerr << endl;
	//you can solve a cycle in O(edges)
	return ans;
	//for each edge:
	//if there is a cycle containing it, you can solve everything on the cycle in O(cycle)
	//otherwise, you know it's good.
	//so if we can decompose the entire tree into cycles/important edges, we get 51
}

Compilation message (stderr)

simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:188:8: warning: variable 'solved' set but not used [-Wunused-but-set-variable]
    int solved = -1;
        ^~~~~~

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