oj.uz

답안 #241174

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
241174 2020-06-23T07:57:45 Z kshitij_sodani 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
0 / 100
 86 ms 145016 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#include "garden.h"

void answer(int x);

//#define endl '\n'
vector<int> adj[3000001];
vector<int> adj2[3000001];
int dist[300001];
int cyc;
vector<pair<int,int>> mi[150001];
void dfs(int no,int levv=0){
	dist[no]=levv;
	for(auto j:adj2[no]){
		if(dist[j]!=-1){
			cyc=levv+1;
		}
		else{
			dfs(j,levv+1);
		}
	}
}
void count_routes(int n,int m,int p,int r[][2],int q,int arr[]){
	
	for(int i=0;i<m;i++){
		mi[r[i][0]].pb({i,r[i][1]});
		mi[r[i][1]].pb({i,r[i][0]});
	}
	for(int i=0;i<n;i++){
		sort(mi[i].begin(),mi[i].end());
	}
	for(int i=0;i<n;i++){
		if(mi[mi[i][0].b][0].a==mi[i][0].a){
			adj[i].pb(n+mi[i][0].b);
		}
		else{
			adj[i].pb(mi[i][0].b);
		}
		int ind=0;
		if(mi[i].size()>1){
			ind=1;
		}
	//	cout<<i<<":"<<ind<<endl;
		if(mi[mi[i][ind].b][0].a==mi[i][ind].a){
			adj[n+i].pb(n+mi[i][ind].b);
		}
		else{
			adj[n+i].pb(mi[i][ind].b);
		}
	}
	for(int i=0;i<2*n;i++){
		for(auto j:adj[i]){
			adj2[j].pb(i);
	//		cout<<i<<","<<j<<endl;
		}
	}
	int ans[q];
	for(int i=0;i<q;i++){
		ans[i]=0;
	}
	for(int ii=0;ii<2;ii++){
		int aa;
		if(ii==0){
			aa=p;
		}
		else{
			aa=p+n;
		}
		for(int i=0;i<2*n;i++){
			dist[i]=-1;
		}
		cyc=-1;
		dfs(aa);
	/*	for(int i=0;i<2*n;i++){
			cout<<dist[i]<<",";
		}
		cout<<endl;
		cout<<cyc<<endl;*/
		for(int j=0;j<q;j++){
			for(int i=0;i<n;i++){
				if(dist[i]==-1){
					continue;
				}
				if(cyc==-1){
					if(dist[i]==arr[j]){
						ans[j]+=1;
					}
				}
				else{
					if(dist[i]==arr[j]){
						ans[j]+=1;
					}
					else if(dist[i]>arr[j]){
						if((dist[i]-arr[j])%cyc==0){
							ans[j]+=1;
						}
					}
				}
			}
		}
	//	cout<<ans[0]<<endl;
	}
	for(int i=0;i<q;i++){
		answer(ans[i]);
	}



}
/*int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);






	return 0;
}*/

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 86 ms 145016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 86 ms 145016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 86 ms 145016 KB Output isn't correct
2 Halted 0 ms 0 KB -