oj.uz

Submission #70961

# Submission time Handle Problem Language Result Execution time Memory
70961 2018-08-23T20:46:45 Z aleksam Tropical Garden (IOI11_garden) C++14
0 / 100
 10 ms 7592 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;
	//if(cyclen[1]>0)cnt[1][0]=1;
	//if(cyclen[0]>0)cnt[0][0]=1;
	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]);
	}
	/*int sum=0;
	for(int i=0; i<2*N; ++i){
		sum+=cnt[i];
	}*/
	//assert(sum==N);
	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){
		if(cyclen[1]==-1)break;
		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;
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:69:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<adj[i].size(); ++j){
                ~^~~~~~~~~~~~~~

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 7592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 7592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 7592 KB Output isn't correct
2 Halted 0 ms 0 KB -