oj.uz

Submission #14694

# Submission time Handle Problem Language Result Execution time Memory
14694 2015-06-05T04:30:38 Z minsu Tropical Garden (IOI11_garden) C++14
49 / 100
 71 ms 14224 KB 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
const int MAXN=1e6;
int elast[MAXN], eprev[MAXN], eadj[MAXN], eind;
int bpath[MAXN][2], bpathn[MAXN];
int L[MAXN], C[MAXN];
void add_edge(int u, int v){
  eadj[eind]=v; eprev[eind]=elast[u]; elast[u]=eind++;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  for(int i=0;i<M;i++){
    int u=R[i][0], v=R[i][1];
    if(bpathn[u]<2) bpath[u][bpathn[u]++]=v;
    if(bpathn[v]<2) bpath[v][bpathn[v]++]=u;
  }
  for(int i=0;i<N;i++) if(bpathn[i]==1) bpath[i][1]=bpath[i][0], bpathn[i]++;
  memset( elast, -1, sizeof elast );
  // Vertex 0 to 2*N-1
  for(int u=0;u<N;u++){
  	if(bpathn[u]==0) continue;
    int F=bpath[u][0], S=bpath[u][1];
    if(bpath[F][0]!=u) add_edge(F*2, u*2); else add_edge(F*2+1, u*2);
    if(bpath[S][0]!=u) add_edge(S*2, u*2+1); else add_edge(S*2+1, u*2+1);
  }
  memset( C, -1, sizeof C );
  queue<int> q; q.push(P*2); q.push(P*2+1);
  L[P*2]=L[P*2+1]=0; C[P*2]=P*2; C[P*2+1]=P*2+1;
  while(!q.empty()){
  	int here=q.front(); q.pop();
  	for(int i=elast[here];i!=-1;i=eprev[i]){
  		int there=eadj[i];
  		L[there]=L[here]+1; C[there]=C[here];
  		if(there/2==P) continue;
  		q.push(there);
  	}
  }
  for(int i=0;i<Q;i++){
  	int ans=0;
  	for(int b=0;b<2*N;b+=2){
  		int g=G[i], bb=b;
  		if(C[bb]==-1) continue;
  		g-=L[bb]; bb=C[bb];
  		if(g>0 && C[bb]!=-1){
	  		if(bb==C[bb]){
	  			g%=L[bb];
	  		}else if(bb!=C[bb]){
	  			g%=(L[bb]+L[C[bb]]);
	  		}
  		}
  		while(g>0 && bb!=-1){
			g-=L[bb]; bb=C[bb];
  		}
  		if(g==0) ans++;
  	}
  	answer(ans);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8136 KB Output is correct
2 Correct 8 ms 8200 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 8 ms 8184 KB Output is correct
5 Correct 9 ms 8160 KB Output is correct
6 Correct 9 ms 8184 KB Output is correct
7 Correct 8 ms 8184 KB Output is correct
8 Correct 9 ms 8188 KB Output is correct
9 Correct 10 ms 8336 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8136 KB Output is correct
2 Correct 8 ms 8200 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 8 ms 8184 KB Output is correct
5 Correct 9 ms 8160 KB Output is correct
6 Correct 9 ms 8184 KB Output is correct
7 Correct 8 ms 8184 KB Output is correct
8 Correct 9 ms 8188 KB Output is correct
9 Correct 10 ms 8336 KB Output is correct
10 Correct 9 ms 8184 KB Output is correct
11 Correct 14 ms 9052 KB Output is correct
12 Correct 24 ms 9820 KB Output is correct
13 Correct 33 ms 11856 KB Output is correct
14 Correct 56 ms 14172 KB Output is correct
15 Correct 71 ms 14224 KB Output is correct
16 Correct 61 ms 12408 KB Output is correct
17 Incorrect 55 ms 12024 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8136 KB Output is correct
2 Correct 8 ms 8200 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 8 ms 8184 KB Output is correct
5 Correct 9 ms 8160 KB Output is correct
6 Correct 9 ms 8184 KB Output is correct
7 Correct 8 ms 8184 KB Output is correct
8 Correct 9 ms 8188 KB Output is correct
9 Correct 10 ms 8336 KB Output is correct
10 Correct 9 ms 8184 KB Output is correct
11 Correct 14 ms 9052 KB Output is correct
12 Correct 24 ms 9820 KB Output is correct
13 Correct 33 ms 11856 KB Output is correct
14 Correct 56 ms 14172 KB Output is correct
15 Correct 71 ms 14224 KB Output is correct
16 Correct 61 ms 12408 KB Output is correct
17 Incorrect 55 ms 12024 KB Output isn't correct
18 Halted 0 ms 0 KB -