oj.uz

답안 #279236

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
279236 2020-08-22T05:13:32 Z TMJN 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
0 / 100
 14 ms 14976 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==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});
    		}
    		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});
    		}
    		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(0);
    	}
    }

Subtask #1
0 / 49.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 31.0

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