oj.uz

답안 #14692

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -