Submission #1305829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305829		lucawaluca	열대 식물원 (Tropical Garden) (IOI11_garden)	C++20	100 / 100	1324 ms	21116 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using ll = long long;

constexpr int INF = 1e9;
using namespace std;
void count_routes(int n, int m, int p, int r[][2], int q, int g[])
{
	vector<vector<array<int, 2>>> grf(n);
	for (int i = 0; i < m; i++)
    {
		grf[r[i][0]].push_back({r[i][1], i});
		grf[r[i][1]].push_back({r[i][0], i});
	}
	vector<vector<array<int,2>>> rev(n);
	for (int i = 0; i < n; i++)
	{
		if (grf[i].size() > 2)
            grf[i].resize(2);
		for (const auto &[j, w] : grf[i])
            rev[j].push_back({i, w});
	}
	vector< array<int,2>> dist(n,{INF,INF});
	vector< array<int,2>> dist2(n,{INF,INF});
	for (int total = 0; total < 2; total++) {
		if (total == 1 && grf[p].size() == 1)
            break;
        queue<array<int,3>> bfs;
		bfs.push({0, p, total});
		while (!bfs.empty())
		{
			const auto [t, u, f] = bfs.front();
			bfs.pop();
			if (dist[u][f]!=INF)
                continue;
			dist[u][f]=t;
			int cum=grf[u][0][1];
			for (const auto &[j, cioara] : rev[u])
			{
				if (f==0&&cioara==cum&&grf[u].size()>1)
                    continue;
				if (f == 1&&cioara!=cum&&grf[u].size()>1)
                    continue;
				int stegulet =(cioara!=grf[j][0][1]);
				bfs.push({t + 1, j, stegulet});
			}
		}
		for (int i = 0; i < n; i++)
            dist2[i][total] = dist[i][0];
		dist.assign(n, {INF, INF});
	}
	const auto get_cycle = [&](int f) ->  array<int, 2>
	{
		int lll = 0;
		int viz = 0;
        vector<array<bool,2>> vis(n);
		int node = p, stegulet = f, ll = 0;
		while (!vis[node][stegulet])
        {
			vis[node][stegulet] = true;
			if (node == p && stegulet == !f)
                viz = ll;
			const auto [urm,cum] = grf[node][stegulet];
			if (grf[urm].size() == 1)
				node = urm, stegulet = 0;
			else{
				node=urm;
				stegulet=(grf[urm][0][1]==cum);
			}
			ll++;
		}
		if (node == p)
            lll=ll;
		else
        {
            lll = INT_MAX;
            viz = 0;
		}
		return {lll, viz};
	};
    array<int,2> v1=get_cycle(0);
    array<int,2> v2={INT_MAX, 0};
	if (grf[p].size() > 1)
        v2 = get_cycle(1);
	for (int j=0;j<q;j++)
    {
		int k = g[j],cnt=0;
		for (int i = 0; i < n; i++)
		{
			if (dist2[i][0]<=k&&((k-dist2[i][0])%v1[0]==0||(k-dist2[i][0])%v1[0]==v1[1]))
				cnt++;
			else if (dist2[i][1]<=k&&((k-dist2[i][1])%v2[0]==0||(k-dist2[i][1])%v2[0]==v2[1]))
				cnt++;
		}
		answer(cnt);
	}
}

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