oj.uz

답안 #278922

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
278922 2020-08-22T04:04:20 Z TMJN 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
0 / 100
 15 ms 14848 KB 
#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==d[i][0].first){
			d[i][0].second=true;
		}
		if(d[d[i][1].first][0].first==d[i][1].first){
			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();
		if(p==pair<int,bool>{-1,0}){
			dd++;
			q.push({-1,0});
		}
		if(!dis[p.first][p.second])continue;
		dis[p.first][p.second]=dd;
		for(auto pp:r[p.first][p.second]){
			q.push(pp);
		}
	}
	q.pop();
	dd=0;
	q.push({P,1});
	q.push({-1,0});
	while(q.size()>=2){
		auto p=q.front();
		if(p==pair<int,bool>{-1,0}){
			dd++;
			q.push({-1,0});
		}
		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]&&(G[i]-dis[j][0])%dis[P][0]==0)||DIS[j][0]==G[i]||(DIS[j][0]<G[i]&&DIS[P][1]&&(G[i]-DIS[j][0])%DIS[P][1]==0)){
				c++;
			}
		}
		answer(c);
	}
}

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 14848 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 14848 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 14848 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -