제출 #92818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92818		ryansee	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	0 / 100	20 ms	16888 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF (long long) 1e18//1234567890987654321
#define INF 1234567890
#define pb push_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos(-1))
#define MAXN 300006
#define MAXK 26
#define MAXX 15000006
#define ll long long int
#define ld long double
#define rep0(kk, l1, l2)for(ll kk = l1; kk < l2; kk++)
#define rep1(kk, l1, l2)for(ll kk = l1; kk <= l2; kk++)
#define foritr(itr, A) for(set<ll>::iterator itr = A.begin(); itr != A.end(); itr++)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ii++)
#define cr(x) cerr << #x << " = " << x << "\n";
#define crA(x, A) cerr << #x << " = " << A[x] << "\n";
#define spacing if(db)cout << " ";
#define mmst(x, v) memset((x), v, sizeof ((x)));
#define bg(ms) (*ms.begin())
#define ed(ms) (*prev(ms.end(), 1))
#define addedge(a, b, c, v) v[(a)].pb(pi((b), (c))); v[(b)].pb(pi((a), (c)))
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n, m, ep, leader[MAXN],co;
vector <ll> v[MAXN], g[MAXN];
ll node[MAXN][2];
vector <pi> edges;
void connect(ll a, ll b)
{
		bool best = (v[a][0] == b);
		if(best)
		{
			// put node (a, 0)
			if(v[b].size() == 1 && v[b][0] == a) 
			{
				// put node(b, 1&0);
				g[node[a][0]].pb(node[b][0]);
				// g[node[a][0]].pb(node[b][1]);
			}
			else if(v[b][0] == a)
			{
				// this edge is his best
				// put node(b, 1)
				g[node[a][0]].pb(node[b][1]);
			}
			else if(v[b][1] == a)
			{
				// can put
				// node(b, 0)
				g[node[a][0]].pb(node[b][0]);
			}
		}
		if(!best && b == v[a][1])
		{
			// put node (a, 1)
			// put node (a, 0)
			if(v[b].size() == 1 && v[b][0] == a) 
			{
				// put node(b, 1&0);
				g[node[a][1]].pb(node[b][0]);
				// g[node[a][1]].pb(node[b][1]);
			}
			else if(v[b][0] == a)
			{
				// this edge is his best
				// put node(b, 1)
				g[node[a][1]].pb(node[b][1]);
			}
			else if(v[b][1] == a)
			{
				// can put
				// node(b, 0)
				g[node[a][1]].pb(node[b][0]);
			}
		}
}
void transverse()
{
	FOR(i,0,MAXN) v[i].clear();
	FOR(i,0,MAXN)
	{
		assert(g[i].size() <= 1);
		for(auto j : g[i])
		{
			v[j].pb(i);
		}
	}
	FOR(i,0,MAXN) g[i].clear();
}
ll dist[MAXN],len;
bool cycle;
void dfs(ll x) // after splitting, there exists only one out-going edge
{
	if(cycle) return;
    assert(v[x].size() <= 1);
	for(auto i : v[x])
	{
		if(cycle) break;
		if(dist[i] != -1 && cycle == 0)
		{
			cycle = 1;  assert(dist[i] == 0);
			len = dist[x] + 1;
			break;
		}
		dist[i] = dist[x] + 1;
		dfs(i);
	}
	if(cycle) return;
}
ll answer_queries[2006];
map <pi, bool> mp;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	n = N, m = M, ep = P;
	FOR(i, 0, n) {node[i][0] = co ++; node[i][1] = co ++;}
	FOR(i, 0, m)
	{
		ll a = R[i][0], b = R[i][1]; bool can = 0;
		if(v[a].size() < 2) can=1,v[a].pb(b);
		if(v[b].size() < 2) can=1,v[b].pb(a);
		if(can) edges.pb(pi(a, b));
	}
	for(auto i : edges)
	{
		ll a = i.f, b = i.s;
		connect(a, b);
		connect(b, a);
	}
	assert(co == n*2);
	transverse();
	mmst(dist, -1);
	dist[node[ep][0]] = 0;
	dfs(node[ep][0]);
	if(cycle)
	{
		FOR(i,0,co)
		{
		    if(dist[i] == -1) continue;
		    assert(dist[i] < len);
		    FOR(j,0,Q)
		    {
				if(dist[i] == G[j]%len && !mp[pi(j, i/2)]) 
				{
					mp[pi(j, i/2)] = 1;
					answer_queries[j] ++;
				}
			}
		}
	}
	else
	{
		FOR(i,0,co)
		{
		    if(dist[i] == -1) continue;
		    // assert(dist[i] < len);
		    FOR(j,0,Q)
		    {
				if(dist[i] == G[j] && !mp[pi(j, i/2)]) 
				{
					mp[pi(j, i/2)] = 1;
					answer_queries[j] ++;
				}
			}
		}
	}
	cycle = 0, len = 0;
	mmst(dist, -1);
	dist[node[ep][1]] = 0;
	dfs(node[ep][1]);
	if(cycle)
	{
		FOR(i,0,co)
		{
		    if(dist[i] == -1) continue;
		    assert(dist[i] < len);
		    FOR(j,0,Q)
		    {
				if(dist[i] == G[j]%len && !mp[pi(j, i/2)]) 
				{
					mp[pi(j, i/2)] = 1;
					answer_queries[j] ++;
				}
			}
		}
	}
	else
	{
		FOR(i,0,co)
		{
		    if(dist[i] == -1) continue;
		    // assert(dist[i] < len);
		    FOR(j,0,Q)
		    {
				if(dist[i] == G[j] && !mp[pi(j, i/2)]) 
				{
					mp[pi(j, i/2)] = 1;
					answer_queries[j] ++;
				}
			}
		}
	}
	FOR(i,0,Q) answer(answer_queries[i]);
}

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31