제출 #241178

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241178		kshitij_sodani	Tropical Garden (IOI11_garden)	C++17	100 / 100	3221 ms	177200 KiB

garden

#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((arr[j]-dist[i])%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: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31