제출 #1266038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266038		PlayVoltz	Tropical Garden (IOI11_garden)	C++20	0 / 100	1 ms	580 KiB

garden

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

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

stack<int> st;
vector<bool> visited, mark;
vector<int> sz, scc;
vector<vector<int> > graph, tgraph, dj;

void dfs(int node, int d, int t){
	if (visited[node])return;
	visited[node]=1;
	dj[t][node]=d;
	for (auto num:graph[node])dfs(num, d+1, t);
	st.push(node);
}

void dfs2(int node, int c){
	if (!visited[node])return;
	if (mark[node])return;
	mark[node]=1;
	scc[node]=c;
	++sz[c];
	for (auto num:tgraph[node])dfs2(num, c);
}

void count_routes(int n, int m, int start, int r[][2], int q, int g[]){
	graph.clear();
	tgraph.clear();
	sz.clear();
	visited.clear();
	scc.clear();
	dj.clear();
	graph.resize(2*n);
	tgraph.resize(2*n);
	vector<vector<pii> > edges(n);
	for (int i=0; i<m; ++i){
		edges[r[i][0]].pb(mp(i, r[i][1]));
		edges[r[i][1]].pb(mp(i, r[i][0]));
	}
	for (int i=0; i<n; ++i)sort(edges[i].begin(), edges[i].end());
	for (int i=0; i<n; ++i){
		graph[i].pb(edges[i][0].se+(edges[edges[i][0].se][0].fi==edges[i][0].fi?n:0));
		tgraph[edges[i][0].se+(edges[edges[i][0].se][0].fi==edges[i][0].fi?n:0)].pb(i);
		if (edges[i].size()>=2){
			graph[i+n].pb(edges[i][1].se+(edges[edges[i][1].se][0].fi==edges[i][1].fi?n:0));
			tgraph[edges[i][1].se+(edges[edges[i][1].se][0].fi==edges[i][1].fi?n:0)].pb(i+n);
		}
		else{
			graph[i+n].pb(edges[i][0].se+(edges[edges[i][0].se][0].fi==edges[i][0].fi?n:0));
			tgraph[edges[i][0].se+(edges[edges[i][0].se][0].fi==edges[i][0].fi?n:0)].pb(i+n);
		}
	}
	swap(graph, tgraph);
	scc.resize(2*n);
	sz.resize(2*n, 0);
	dj.resize(2, vector<int>(2*n, -1));
	visited.resize(2*n, 0);
	dfs(start, 0, 0);
	mark.clear();
	mark.resize(2*n, 0);
	while (st.size()){
		int node=st.top();
		st.pop();
		if (mark[node])continue;
		dfs2(node, node);
	}
	visited.assign(2*n, 0);
	dfs(start+n, 0, 1);
	while (st.size())st.pop();
	for (int i=0; i<q; ++i){
		int ans=0;
		for (int j=0; j<n; ++j){
			bool can=0;
			for (int p=0; p<2; ++p){
				if (dj[p][j]==-1)continue;
				if (sz[scc[start+p*n]]==1){
					if (dj[p][j]==g[i])can=1;
				}
				else if (dj[p][j]<=g[i]&&!((g[i]-dj[p][j])%sz[scc[start+p*n]]))can=1;
			}
			
			ans+=can;
		}
		answer(ans);
	}
}

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