Submission #279302

#	Time	Username	Problem	Language	Result	Execution time	Memory
279302		TMJN	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	100 / 100	2904 ms	24580 KiB

garden

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

pair<int,bool>d[150000][2];
int dis[150000][2],DIS[150000][2];
vector<pair<int,bool>>r[150000][2];


void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	for(int i=0;i<N;i++){
		d[i][0]=d[i][1]={-1,0};
	}
	for(int i=0;i<M;i++){
		int p=R[i][0];
		int q=R[i][1];
		if(d[p][0].first==-1){
			d[p][0].first=q;
		}
		else if(d[p][1].first==-1){
			d[p][1].first=q;
		}
		swap(p,q);
		if(d[p][0].first==-1){
			d[p][0].first=q;
		}
		else if(d[p][1].first==-1){
			d[p][1].first=q;
		}
	}
	for(int i=0;i<N;i++){
		if(d[d[i][0].first][0].first==i){
			d[i][0].second=true;
		}
		if(d[i][1].first==-1){
			d[i][1].first=d[i][0].first;
		}
		if(d[d[i][1].first][0].first==i){
			d[i][1].second=true;
		}
		r[d[i][0].first][d[i][0].second].push_back({i,0});
		r[d[i][1].first][d[i][1].second].push_back({i,1});
	}
	queue<pair<int,bool>>q;
	q.push({P,0});
	q.push({-1,0});
	int dd=0;
	while(q.size()>=2){
		auto p=q.front();
		q.pop();
		if(p==pair<int,bool>{-1,0}){
			dd++;
			q.push({-1,0});
			continue;
		}
		if(dis[p.first][p.second])continue;
		dis[p.first][p.second]=dd;
		for(auto pp:r[p.first][p.second]){
			q.push(pp);
		}
	}
	queue<pair<int,bool>>qq;
	swap(q,qq);
	dd=0;
	q.push({P,1});
	q.push({-1,0});
	while(q.size()>=2){
		auto p=q.front();
		q.pop();
		if(p==pair<int,bool>{-1,0}){
			dd++;
			q.push({-1,0});
			continue;
		}
		if(DIS[p.first][p.second])continue;
		DIS[p.first][p.second]=dd;
		for(auto pp:r[p.first][p.second]){
			q.push(pp);
		}
	}
	for(int i=0;i<Q;i++){
		int c=0;
		for(int j=0;j<N;j++){
			if(dis[j][0]==G[i]||(dis[j][0]<G[i]&&dis[P][0]&&dis[j][0]&&(G[i]-dis[j][0])%dis[P][0]==0)||DIS[j][0]==G[i]||(DIS[j][0]<G[i]&&DIS[P][1]&&DIS[j][0]&&(G[i]-DIS[j][0])%DIS[P][1]==0)){
				c++;
			}
		}
		answer(c);
	}
}

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