Submission #1185100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185100		prism7k	Tropical Garden (IOI11_garden)	C++20	49 / 100	65 ms	33864 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300000;
vector<vector<pair<int, int>>> conn(MAXN);
vector<vector<int>> adjT(MAXN);
const int pr = 150000;

int T[MAXN][2];
bool vis[MAXN][2];
bool on_cycle[2];
int C_Len = 2e9+5;

void dfs(int u, int cur, int idx, int start) {
	if(u == start && vis[u][idx]) {
		C_Len = cur;
		on_cycle[idx] = true;
		return;
	}
	if(vis[u][idx]) return;
	vis[u][idx] = true;
	T[u][idx] = cur;
	for(int v : adjT[u]) {
		dfs(v, cur + 1, idx, start);
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	memset(T, -1, sizeof T);
	for(int i = 0, a, b; i < M; ++i) {
		a = R[i][0];
		b = R[i][1];
		conn[a].push_back({i, b});
		conn[b].push_back({i, a});
	}
	
	for(int i = 0; i < N; ++i) sort(conn[i].begin(), conn[i].end());
	
	for(int i = 0; i < N; ++i) {
		int j, dest, idx;
		bool usedBest;
		
		j = conn[i][0].second;
		usedBest = false;
		if (conn[j][0].second == i) usedBest = true;
		dest = usedBest ? j + pr : j;
		adjT[dest].push_back(i);
		
		idx = (conn[i].size() > 1 ? 1 : 0);
		j = conn[i][idx].second;
		usedBest = false;
		if (conn[j][0].second == i) usedBest = true;
		dest = usedBest ? j + pr : j;
		adjT[dest].push_back(i + pr);
	}
	
	dfs(P, 0, 0, P);
	dfs(P + pr, 0, 1, P + pr);
	
	for(int k = 0; k < Q; ++k) {
		int g = G[k];
		int ans = 0;
		for(int i = 0; i < N; ++i) {
			bool ok = false;
			for(int j = 0; j < 2; ++j) {
				if(T[i][j] == -1 || g < T[i][j]) continue;
				if(on_cycle[j]) {
					ok |= ((g - T[i][j]) % C_Len) == 0;
				} else {
					ok |= (g - T[i][j]) == 0;
				}
			}
			ans += ok;
		}
		answer(ans);
	}
}

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