제출 #50977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50977		win11905	열대 식물원 (Tropical Garden) (IOI11_garden)	C++11	69 / 100	1743 ms	38984 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int MXN = 1.5e5+5, INF = 1e9;

pii MinPath[MXN][2], rot[MXN][2];
int d[MXN][2], deg[MXN][2], pos[MXN][2], com[MXN][2];
bool iscycle[MXN][2];
vector<pii> g[MXN][2], rg[MXN][2];
vector<vector<pii> > comp;

void fill_tree(pii u, pii p, pii root) {
	rot[u.x][u.y] = root, d[u.x][u.y] = d[p.x][p.y] + 1;
	for(pii v : rg[u.x][u.y]) if(!iscycle[v.x][v.y] and v != p) fill_tree(v, u, root);
}

void count_routes(int N, int M, int P, int R[][2], int Qq, int G[]) {
	fill(MinPath[0], MinPath[N-1] + 2, pii(INF, -1));
	for(int i = 0; i < M; ++i) {
		int u = R[i][0], v = R[i][1];
		pii a(i, v), b(i, u);
		if(MinPath[u][0] > a) swap(MinPath[u][0], a);
		if(MinPath[u][1] > a) swap(MinPath[u][1], a);
		if(MinPath[v][0] > b) swap(MinPath[v][0], b);
		if(MinPath[v][1] > b) swap(MinPath[v][1], b);
	}
	for(int i = 0; i < N; ++i) {
		if(MinPath[i][1].x == INF) MinPath[i][1] = MinPath[i][0];
		g[i][0].emplace_back(MinPath[i][0].y, MinPath[MinPath[i][0].y][0].x == MinPath[i][0].x);
		g[i][1].emplace_back(MinPath[i][1].y, MinPath[MinPath[i][1].y][0].x == MinPath[i][1].x);
	}
	// for(int i = 0; i < N; ++i) for(int j = 0; j < 2; ++j) printf("%d %d :: %d %d\n", i, j, g[i][j][0].x, g[i][j][0].y);
	/***************************** find cycle *******************************/
	for(int i = 0; i < N; ++i) {
		for(auto x : g[i][0]) deg[x.x][x.y]++, rg[x.x][x.y].emplace_back(i, 0);
		for(auto x : g[i][1]) deg[x.x][x.y]++, rg[x.x][x.y].emplace_back(i, 1);
	}
	queue<pii> Q;
	for(int i = 0; i < N; ++i) {
		if(!deg[i][0]) Q.emplace(i, 0);
		if(!deg[i][1]) Q.emplace(i, 1);
	}
	while(!Q.empty()) {
		pii now = Q.front(); Q.pop();
		for(pii v : g[now.x][now.y]) if(deg[v.x][v.y] >= 1) {
			deg[v.x][v.y]--;
			if(!deg[v.x][v.y]) Q.emplace(v.x, v.y); 
		}
	}
	d[MXN-1][0] = -1;
	for(int i = 0; i < N; ++i) for(int j = 0; j < 2; ++j) {
		if(deg[i][j] == 1) deg[i][j]--, Q.emplace(i, j);
		else continue;
		comp.emplace_back(vector<pii>());
		while(!Q.empty()) {
			pii now = Q.front(); Q.pop();
			com[now.x][now.y] = comp.size()-1;
			pos[now.x][now.y] = comp.back().size();
			iscycle[now.x][now.y] = true;
			comp.back().emplace_back(now.x, now.y);
			for(pii v : g[now.x][now.y]) if(!--deg[v.x][v.y]) Q.emplace(v.x, v.y);
		} 
		for(auto x : comp.back()) fill_tree(x, pii(MXN-1, 0), x);
	}
	// cout << comp.size() << endl;
	// for(auto x : comp[0]) cout << x.x << x.y << endl;
	/************************** end **************************************/
	vector<int> dis[2];
	auto Merge = [&](pii a, pii b) {
		if(iscycle[b.x][b.y]) {
			pii root = rot[a.x][a.y];
			if(com[root.x][root.y] != com[b.x][b.y]) return;
			int d_to_rot = d[a.x][a.y];
			// cout << a.x << ' ' << d_to_rot << endl;
			if(pos[root.x][root.y] <= pos[b.x][b.y]) d_to_rot += pos[b.x][b.y] - pos[root.x][root.y];
			else d_to_rot += (int)comp[com[b.x][b.y]].size() - (pos[root.x][root.y] - pos[b.x][b.y]);
			dis[b.y].emplace_back(d_to_rot);
		} else {
			if(rot[a.x][a.y] != rot[b.x][b.y]) return;
			int d_to_pos = d[a.x][a.y] - d[b.x][b.y];
			dis[b.y].emplace_back(d_to_pos);
		}
	};
	for(int i = 0; i < N; ++i) for(int k = 0; k < 2; ++k) {
		Merge(pii(i, 0), pii(P, k));
	}
	// for(auto x : dis[0]) cout << x << endl;
	/*****************************************************************/
	for(int i = 0; i < Qq; ++i) {
		int len = G[i], sum = 0;
		auto f = [&](bool st) {
			for(int x : dis[st]) if(iscycle[P][st]) {
				if(len - x >= 0 and ((len - x) % (int)comp[com[P][st]].size()) == 0) sum++;
			} else if(x == len) sum++;
		};
		f(0), f(1);
		answer(sum);
	}
}

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