Submission #14689

#	Time	Username	Problem	Language	Result	Execution time	Memory
14689		minsu	Tropical Garden (IOI11_garden)	C++14	49 / 100	29 ms	8544 KiB

garden

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include "garden.h"
#include "gardenlib.h"
#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);
  }
  queue<int> q; q.push(P*2); q.push(P*2+1);
  L[P*2]=L[P*2+1]=0; C[P*2]=0; C[P*2+1]=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);
  	}
  }
  int eaten = ( C[P*2]==1 ? 0 : 1);
  for(int i=0;i<Q;i++){
  	int ans=0;
  	for(int b=0;b<2*N;b+=2){
  		int g=G[i];
  		if(g==L[b]) { ans++; continue; }
  		if(C[b]==eaten){
  			g-=L[b]; g-=L[P*2+eaten];
  		}else{
  			g-=L[b];
  		}
  		if(g>=0 && g%L[P*2+(eaten^1)]==0) ans++;
  	}
  	answer(ans);
  }
}

• Subtask 1: 49 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31