oj.uz

답안 #70940

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
70940 2018-08-23T19:42:51 Z aleksam 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
0 / 100
 9 ms 7516 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, num;
int cnt[2*MAX_N];
int cumcnt[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=dist[num][u]+1;
		}
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){int valu=1/0;
	//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][0]][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=-1;
	dist[0][P]=0;
	DFS(P);
	num=1;
	mark[1][P+N]=1;
	p=P+N;
	dist[1][P+N]=0;
	DFS(P+N);
	for(int i=0; i<N; ++i){
		//printf("dist:%d %d\n", dist[0][i], dist[1][i]);
		
		if(i<N){
			cnt[dist[0][i]]++;
			cnt[dist[1][i]]++;
		}
	}
	/*for(int i=0; i<N; ++i){
		printf("cnt:%d\n", cnt[i]);
	}*/
	cnt[0]=1;
	if(cyclen==-1){
		for(int i=0; i<Q; ++i){
			answer(cnt[G[i]]);
			//cout<<cnt[G[i]];
		}
		return;
	}
	for(int i=0; i<2*N; ++i){
		cumcnt[i]=cnt[i];
		if(i>=cyclen)
			cumcnt[i]+=cumcnt[i-cyclen];
	}
	for(int i=0; i<Q; ++i){
		if(G[i]>=2*N){
			
			int val=G[i]%cyclen + 2*N - (2*N)%cyclen;
			while(val>2*N)val-=cyclen;
			answer(cumcnt[ val]);
			//cout<<cumcnt[ G[i]%cyclen+2*N-cyclen];
		}
		else {
			answer(cumcnt[G[i]]);
			//cout<<cumcnt[G[i]];
		}
	}
	return;
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:29:78: warning: division by zero [-Wdiv-by-zero]
 void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){int valu=1/0;
                                                                             ~^~
garden.cpp:29:72: warning: unused variable 'valu' [-Wunused-variable]
 void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){int valu=1/0;
                                                                        ^~~~

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7516 KB Output is correct
2 Correct 9 ms 7508 KB Output is correct
3 Correct 9 ms 7516 KB Output is correct
4 Incorrect 8 ms 7388 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7516 KB Output is correct
2 Correct 9 ms 7508 KB Output is correct
3 Correct 9 ms 7516 KB Output is correct
4 Incorrect 8 ms 7388 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7516 KB Output is correct
2 Correct 9 ms 7508 KB Output is correct
3 Correct 9 ms 7516 KB Output is correct
4 Incorrect 8 ms 7388 KB Output isn't correct
5 Halted 0 ms 0 KB -