oj.uz

Submission #14692

# Submission time Handle Problem Language Result Execution time Memory
14692 2015-06-05T04:15:16 Z minsu Tropical Garden (IOI11_garden) C++14
49 / 100
 5000 ms 14072 KB 
#include <cstdio>
#include <cstring>
#include "garden.h"
#include "gardenlib.h"
#include <cstdlib>
#include <queue>
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]; 
  		// if(C[there]!=-1) continue;
  		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;
  		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 9 ms 8144 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 9 ms 8188 KB Output is correct
5 Correct 8 ms 8184 KB Output is correct
6 Correct 9 ms 8184 KB Output is correct
7 Correct 9 ms 8184 KB Output is correct
8 Correct 9 ms 8284 KB Output is correct
9 Correct 10 ms 8312 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8144 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 9 ms 8188 KB Output is correct
5 Correct 8 ms 8184 KB Output is correct
6 Correct 9 ms 8184 KB Output is correct
7 Correct 9 ms 8184 KB Output is correct
8 Correct 9 ms 8284 KB Output is correct
9 Correct 10 ms 8312 KB Output is correct
10 Correct 9 ms 8184 KB Output is correct
11 Correct 17 ms 9128 KB Output is correct
12 Correct 53 ms 9820 KB Output is correct
13 Correct 2243 ms 11896 KB Output is correct
14 Execution timed out 5049 ms 14072 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8144 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 9 ms 8188 KB Output is correct
5 Correct 8 ms 8184 KB Output is correct
6 Correct 9 ms 8184 KB Output is correct
7 Correct 9 ms 8184 KB Output is correct
8 Correct 9 ms 8284 KB Output is correct
9 Correct 10 ms 8312 KB Output is correct
10 Correct 9 ms 8184 KB Output is correct
11 Correct 17 ms 9128 KB Output is correct
12 Correct 53 ms 9820 KB Output is correct
13 Correct 2243 ms 11896 KB Output is correct
14 Execution timed out 5049 ms 14072 KB Time limit exceeded
15 Halted 0 ms 0 KB -