Submission #7882

#	Time	Username	Problem	Language	Result	Execution time	Memory
7882		dohyun0324	Tropical Garden (IOI11_garden)	C++98	100 / 100	3763 ms	16428 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<algorithm>
#include<string.h>
using namespace std;
int sw,sx,sp,x,y,top,w,n,m,p,con[300010][2],cnt,g[300010],q,d[300010][2],leng[300010][2],ch[300010][2],dap[2010];
struct data2{
	int x,p;
}sav[300010];
struct data{
	int x,y,c;
	bool operator<(const data&r)const
	{
		if(x==r.x) return c<r.c;
		return x<r.x;
	}
}arr[300010];
void dfs(int x,int k)
{
    int i;
    if(ch[x][k]==cnt){sw=1; sx=x; sp=k; return;}
    if(ch[x][k]!=cnt && ch[x][k]!=0){sw=2; sx=x; sp=k; return;}
    ch[x][k]=cnt;
    top++; sav[top].x=x; sav[top].p=k;
    if(con[con[x][k]][1]==0) dfs(con[x][k],0);
    else if(con[con[x][k]][0]==x) dfs(con[x][k],1);
    else dfs(con[x][k],0);
}
void put(int t)
{
    int i,j,k,c=0;
    if(sw==1){
        for(i=1;i<=top;i++) if(sav[i].x==p && sav[i].p==t) break;
        if(i==top+1) return;
        for(j=1;j<=top;j++) if(sav[j].x==sx && sav[j].p==sp) break;
        if(i>=j){
            for(k=i-1;k!=i;k--){
                if(k==j-1) k=top;
                d[sav[k].x][sav[k].p]=++c;
                leng[sav[k].x][sav[k].p]=top-i+1;
            }
            leng[p][t]=top-i+1;
        }
        else{
            for(k=i-1;k>=1;k--) d[sav[k].x][sav[k].p]=++c;
        }
    }
    else{
        if(!(sx==p && sp==t) && d[sx][sp]==0) return;
        for(i=top;i>=1;i--){
            c++;
            d[sav[i].x][sav[i].p]=d[sx][sp]+c;
            leng[sav[i].x][sav[i].p]=leng[sx][sp];
        }
    }
}
void query()
{
    int i,j,k;
    top=0; cnt++; dfs(p,0); put(0);
    for(i=1;i<=n;i++){
        top=0; cnt++; dfs(i,0); put(0);
        top=0; cnt++; dfs(i,1); put(0);
    }
    for(k=1;k<=2;k++){
        for(i=1;i<=q;i++){
            for(j=1;j<=n;j++){
                if(leng[j][0]==0 && d[j][0]==g[i]) dap[i]++;
                if(leng[j][0]!=0 && d[j][0]<=g[i] && (g[i]-d[j][0])%leng[j][0]==0) dap[i]++;
            }
        }
        cnt=0; memset(d,0,sizeof d); memset(leng,0,sizeof leng); memset(ch,0,sizeof ch); memset(sav,0,sizeof sav);
        top=0; cnt++; dfs(p,1); put(1);
        for(i=1;i<=n;i++){
            top=0; cnt++; dfs(i,0); put(1);
            top=0; cnt++; dfs(i,1); put(1);
        }
    }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    int i;
    n=N; m=M; p=P+1; q=Q;
	for(i=1;i<=m;i++)
	{
	    x=R[i-1][0]+1; y=R[i-1][1]+1;
		w++; arr[w].x=x; arr[w].y=y; arr[w].c=i;
		w++; arr[w].x=y; arr[w].y=x; arr[w].c=i;
	}
    for(i=1;i<=q;i++) g[i]=G[i-1];
	sort(arr+1,arr+w+1);
	for(i=1;i<=w;i++){
		if(arr[i].x!=arr[i-1].x){
			con[arr[i].x][0]=arr[i].y;
			if(arr[i].x==arr[i+1].x) con[arr[i].x][1]=arr[i+1].y;
		}
	}
	query();
    for(i=1; i<=Q; i++)
        answer(dap[i]);
}

Compilation message (stderr)

garden.cpp: In function 'void dfs(int, int)':
garden.cpp:20:9: warning: unused variable 'i' [-Wunused-variable]
     int i;
         ^

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