Submission #242667

#	Time	Username	Problem	Language	Result	Execution time	Memory
242667		johutha	Tropical Garden (IOI11_garden)	C++17	69 / 100	5050 ms	54820 KiB

garden

#pragma GCC optimize("Ofast")

#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <iostream>
 
using namespace std;
 
struct graph
{
	int n;
	int h;
	vector<vector<int>> adjlist;
	vector<vector<int>> best;
	vector<int> dist;
	vector<bool> cycle;
	int cyc = 2e9;
	int p;
 
	void add(int fr, int to)
	{
		int t = to;
		if (fr == best[to][0]) t += h;
		if (best[fr][0] == to)
		{
			adjlist[fr].push_back(t);
		}
		if (best[fr][1] == to)
		{
			adjlist[fr + h].push_back(t);
		}
	}
 
	graph(int in, int m, vector<vector<int>> ib, int R[][2]) : n(2*in), h(in), adjlist(vector<vector<int>>(2*n)), best(ib), dist(n, -1), cycle(n)
	{
		for (int i = 0; i < m; i++)
		{
			add(R[i][0], R[i][1]);
			add(R[i][1], R[i][0]);
		}
	}
 
	void print()
	{
		cout << n << "\n";
 
		for (int i = 0; i < n; i++)
		{
			for (auto j : adjlist[i])
			{
				cout << i << " " << j << "\n";
			}
		}
	}
 
	void reverse()
	{
		vector<vector<int>> old(n);
		swap(old, adjlist);
 
		for (int i = 0; i < n; i++)
		{
			for (int j : old[i])
			{
				adjlist[j].push_back(i);
			}
		}
	}
 
	bool dfs(int curr, int d)
	{
		if (curr == p && dist[curr] != -1)
		{
			cyc = d;
			return true;
		}
		dist[curr] = d;
 
		for (auto next : adjlist[curr])
		{
			if (dfs(next, d + 1)) cycle[curr] = true;
		}
 
		return cycle[curr];
	}
	
	void calc(int P)
	{
		p = P;
		dfs(p, 0);
	}
 
	void pcyc()
	{
		cout << "Cycle: " << cyc << "\n";
		for (int i = 0; i < n; i++)
		{
			cout << (i % h);
			if (i >= h) cout << "*";
			else cout << " ";
			cout << ": ";
			cout << cycle[i] << "   " << dist[i] << "\n";
		}
	}
 
	bool check(int v, int t)
	{
		if (t < dist[v]) return false;
		if (t % cyc != dist[v] % cyc) return false;
		return true;
	}
};
 
void count_routes(int n, int m, int P, int R[][2], int Q, int G[])
{
	vector<vector<int>> best(n, vector<int>(2, -1));
 
	auto ins = [&](int k, int v)
	{
		swap(best[k][0], best[k][1]);
		best[k][0] = v;
	};
 
	for (int i = m - 1; i >= 0; i--)
	{
		ins(R[i][0], R[i][1]);
		ins(R[i][1], R[i][0]);
	}
 
	for (int i = 0; i < n; i++) if (best[i][1] == -1) best[i][1] = best[i][0];
 
	graph g(n, m, best, R);
	g.reverse();
	graph g2(g);
	g.calc(P);
	g2.calc(P + n);
	
	for (int c = 0; c < Q; c++)
	{
		int v = G[c];
		int r = 0;
 
		for (int i = 0; i < n; i++)
		{
			r += g.check(i, v);
			r += g2.check(i, v);
		}
		answer(r);
	}
}

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