oj.uz

Submission #70948

# Submission time Handle Problem Language Result Execution time Memory
70948 2018-08-23T20:14:10 Z aleksam Tropical Garden (IOI11_garden) C++14
49 / 100
 135 ms 25496 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[]){
	//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=-1;
	dist[0][P]=0;
	DFS(P);
	if(cyclen!=-1)dist[0][P]=cyclen;
	//cout<<cyclen<<endl;
	num=1;
	mark[1][P+N]=1;
	p=P+N;
	dist[1][P+N]=0;
	DFS(P+N);
	//cout<<cyclen<<endl;
	for(int i=0; i<2*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;
	int sum=0;
	for(int i=0; i<2*N; ++i){
		sum+=cnt[i];
	}
	//assert(sum==N);
	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){
			//assert(1==0);
			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;
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Output is correct
2 Correct 9 ms 7568 KB Output is correct
3 Correct 9 ms 7488 KB Output is correct
4 Correct 8 ms 7388 KB Output is correct
5 Correct 14 ms 7444 KB Output is correct
6 Correct 9 ms 7644 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 11 ms 7676 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Output is correct
2 Correct 9 ms 7568 KB Output is correct
3 Correct 9 ms 7488 KB Output is correct
4 Correct 8 ms 7388 KB Output is correct
5 Correct 14 ms 7444 KB Output is correct
6 Correct 9 ms 7644 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 11 ms 7676 KB Output is correct
10 Correct 8 ms 7396 KB Output is correct
11 Correct 18 ms 9304 KB Output is correct
12 Correct 31 ms 10624 KB Output is correct
13 Correct 61 ms 25496 KB Output is correct
14 Correct 94 ms 17760 KB Output is correct
15 Correct 135 ms 18704 KB Output is correct
16 Correct 100 ms 15176 KB Output is correct
17 Incorrect 87 ms 14784 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Output is correct
2 Correct 9 ms 7568 KB Output is correct
3 Correct 9 ms 7488 KB Output is correct
4 Correct 8 ms 7388 KB Output is correct
5 Correct 14 ms 7444 KB Output is correct
6 Correct 9 ms 7644 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 11 ms 7676 KB Output is correct
10 Correct 8 ms 7396 KB Output is correct
11 Correct 18 ms 9304 KB Output is correct
12 Correct 31 ms 10624 KB Output is correct
13 Correct 61 ms 25496 KB Output is correct
14 Correct 94 ms 17760 KB Output is correct
15 Correct 135 ms 18704 KB Output is correct
16 Correct 100 ms 15176 KB Output is correct
17 Incorrect 87 ms 14784 KB Output isn't correct
18 Halted 0 ms 0 KB -