Submission #551234

#	Time	Username	Problem	Language	Result	Execution time	Memory
551234		ymm	Tropical Garden (IOI11_garden)	C++17	49 / 100	116 ms	42676 KiB

garden

///
///   There's a reason for your defeat, DIO. One simple reason...
///   You pissed me off.
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

#ifndef DARD
#include "garden.h"
#include "gardenlib.h"
#else
void answer(int x)
{
	cout << x << ' ';
}
#endif

const int N = 150'010;
vector<int> T[2*N];
int A[2*N];
int deg[2*N], cnt[2*N];

void add_edge(int v, int u)
{
	A[v] = u;
	T[u].push_back(v);
}

int ans[N];
int q, g[N];

bool cyc[2*N];

void dfs(int v, int d)
{
	cnt[d] += v >= N;
	for (int u : T[v])
		dfs(u, d+1);
}

vector<int> vmod[2*N];
int cycs;

void dfs2(int v, int d, int rt)
{
	if (v >= N)
		vmod[d%cycs].push_back(d);
	for (int u : T[v])
		if (u != rt)
			dfs2(u, d+1, rt);
}

void solve(int v)
{
	memset(cyc, 0, sizeof(cyc));
	int u = v;
	cycs = 0;
	do {
		cyc[u] = 1;
		u = A[u];
		++cycs;
	} while (!cyc[u]);
	if (u != v) {
		memset(cnt, 0, sizeof(cnt));
		dfs(v, 0);
		Loop (i,0,q)
			ans[i] += cnt[g[i]];
	} else {
		Loop (i,0,cycs)
			vmod[i].clear();
		dfs2(v, 0, v);
		Loop (i,0,cycs)
			sort(vmod[i].begin(), vmod[i].end());
		Loop (i,0,q) {
			int gm = g[i]%cycs;
			ans[i] += upper_bound(vmod[gm].begin(),
			              vmod[gm].end(), g[i]) - vmod[gm].begin();
		}
	}
}

void count_routes(int n, int m, int p, int r[][2], int q, int g[])
{
	Loop (i,0,m) {
		deg[r[i][0]]++;
		deg[r[i][1]]++;
	}
	Loop (i,0,m) {
		for (auto [v, u] : {pii{r[i][0], r[i][1]}, pii{r[i][1], r[i][0]}}) {
			if ((cnt[v] == 1 || deg[v] == 1) && cnt[u] == 0) // F F
				add_edge(v, u);
			if ((cnt[v] == 1 || deg[v] == 1) && cnt[u] != 0) // F nF
				add_edge(v, u+N);
			if (cnt[v] == 0 && cnt[u] == 0) // nF F
				add_edge(v+N, u);
			if (cnt[v] == 0 && cnt[u] != 0) // nF nF
				add_edge(v+N, u+N);
		}
		cnt[r[i][0]]++;
		cnt[r[i][1]]++;
	}
	::q = q;
	Loop (i,0,q) ::g[i] = g[i];
	solve(p);
	solve(p+N);
	Loop (i,0,q)
		answer(ans[i]);
}

#ifdef DARD
int main()
{
//	int constexpr n = 6;
//	int constexpr m = 6;
//	int constexpr p = 0;
//	int constexpr q = 1;
//	int g[q] = {3};
//	int r[m][2] = {{1,2}, {0,1}, {0,3}, {3,4}, {4,5}, {1,5}};
	int constexpr n = 5;
	int constexpr m = 5;
	int constexpr p = 2;
	int constexpr q = 2;
	int g[q] = {3, 1};
	int r[m][2] = {{1,0}, {1,2}, {3,2}, {1,3}, {4,2}};
	count_routes(n, m, p, r, q, g);
	cout << '\n';
}
#endif

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