oj.uz

답안 #71436

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
71436 2018-08-24T14:44:27 Z aleksam 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
0 / 100
 9 ms 7544 KB 
#include <bits/stdc++.h>
#include "gardenlib.h"
#define MAX_N 150000

using namespace std;

vector<int> adj[MAX_N*2];
int best[MAX_N][2];
int dist[2][2*MAX_N];
bool mark[2][2*MAX_N];
int p, cyclen[2], num;
int cnt[2][2*MAX_N];
int cumcnt[2][2*MAX_N];

void DFS(int u){
	int d=adj[u].size();
	for(int i=0; i<d; ++i){
		if(!mark[num][adj[u][i]]){
			mark[num][adj[u][i]]=1;
			dist[num][adj[u][i]]=dist[num][u]+1;
			DFS(adj[u][i]);
		}
		if(adj[u][i]==p){
			cyclen[num]=dist[num][u]+1;
		}
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	//u adj cuvamo sva temena koja se ulivaju u i
	//prvo odredjujemo najlepse putanje svakom temenu
	for(int i=0; i<N; ++i){
		best[i][0]=best[i][1]=-1;
	}
	for(int i=0; i<M; ++i){
		if(best[R[i][0]][0]==-1){
			best[R[i][0]][0]=R[i][1];
		}
		else{
			if(best[R[i][0]][1]==-1){
				best[R[i][0]][1]=R[i][1];
			}
		}
		if(best[R[i][1]][0]==-1){
			best[R[i][1]][0]=R[i][0];
		}
		else{
			if(best[R[i][1]][1]==-1){
				best[R[i][1]][1]=R[i][0];
			}
		}
	}
	for(int i=0; i<N; ++i){
		//Odredjujemo gde ide cvor i
		if(best[best[i][0]][0]==i && best[best[i][0]][1]!=-1){
			adj[best[i][0]+N].push_back(i);
		}
		else
			adj[best[i][0]].push_back(i);
		if(best[i][1]==-1)continue;
		if(best[best[i][1]][0]==i && best[best[i][1]][1]!=-1){
			adj[best[i][1]+N].push_back(i+N);
		}
		else
			adj[best[i][1]].push_back(i+N);
	}
	/*for(int i=0; i<2*N; ++i){
		printf("adj[%d]:", i);
		for(int j=0; j<adj[i].size(); ++j){
			printf("%d ", adj[i][j]);
		}
		printf("\n");
	}*/
	mark[0][P]=1;
	p=P;
	cyclen[0]=cyclen[1]=-1;
	dist[0][P]=0;
	DFS(P);
	//cout<<cyclen[0]<<endl;
	num=1;
	mark[1][P+N]=1;
	p=P+N;
	dist[1][P+N]=0;
	DFS(P+N);
	//cout<<cyclen[1]<<endl;
	for(int i=0; i<2*N; ++i){
		//printf("dist:%d %d\n", dist[0][i], dist[1][i]);
		
		if(i<N){
			if(dist[0][i])
				cnt[0][dist[0][i]]++;
			if(dist[1][i])
				cnt[1][dist[1][i]]++;
		}
	}
	for(int i=0; i<N; ++i){
		//printf("cnt:%d %d\n", cnt[0][i], cnt[1][i]);
	}
	if(cyclen[0]==-1 && cyclen[1]==-1){
		for(int i=0; i<Q; ++i){
			answer(cnt[0][G[i]]+cnt[1][G[i]]);
			//cout<<cnt[G[i]];
		}
		return;
	}
	for(int i=0; i<2*N; ++i){
		cumcnt[0][i]=cnt[0][i];
		if(i>=cyclen[0] && cyclen[0]!=-1)
			cumcnt[0][i]+=cumcnt[0][i-cyclen[0]];
	}
	for(int i=0; i<2*N; ++i){
		cumcnt[1][i]=cnt[1][i];
		if(i>=cyclen[1] && cyclen[1]!=-1)
			cumcnt[1][i]+=cumcnt[1][i-cyclen[1]];
	}
	for(int i=0; i<3*N; ++i){
		//printf("cumcnt:%d %d\n", cumcnt[0][i], cumcnt[1][i]);
	}
	int cyc=max(cyclen[0], cyclen[1]);
	for(int i=0; i<Q; ++i){
		if(G[i]>=2*N){
			int val=G[i]%cyc + 2*N - ((2*N)%cyc);
			while(val>=2*N)val-=cyc;
			answer(cumcnt[0][val]+cumcnt[1][val]);
			//cout<<cumcnt[ G[i]%cyclen+2*N-cyclen];
		}
		else {
			answer(cumcnt[0][G[i]]+cumcnt[1][G[i]]);
			//cout<<cumcnt[G[i]];
		}
	}
	return;
}

Subtask #1
0 / 49.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 31.0

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