oj.uz

Submission #7882

# Submission time Handle Problem Language Result Execution time Memory
7882 2014-08-22T14:08:39 Z dohyun0324 Tropical Garden (IOI11_garden) C++
100 / 100
 3763 ms 16428 KB 
#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

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

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9824 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 11 ms 9720 KB Output is correct
4 Correct 11 ms 9720 KB Output is correct
5 Correct 14 ms 9692 KB Output is correct
6 Correct 12 ms 9864 KB Output is correct
7 Correct 12 ms 9692 KB Output is correct
8 Correct 12 ms 9820 KB Output is correct
9 Correct 15 ms 9976 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9824 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 11 ms 9720 KB Output is correct
4 Correct 11 ms 9720 KB Output is correct
5 Correct 14 ms 9692 KB Output is correct
6 Correct 12 ms 9864 KB Output is correct
7 Correct 12 ms 9692 KB Output is correct
8 Correct 12 ms 9820 KB Output is correct
9 Correct 15 ms 9976 KB Output is correct
10 Correct 11 ms 9720 KB Output is correct
11 Correct 22 ms 10864 KB Output is correct
12 Correct 43 ms 12024 KB Output is correct
13 Correct 47 ms 13404 KB Output is correct
14 Correct 107 ms 15612 KB Output is correct
15 Correct 116 ms 15776 KB Output is correct
16 Correct 106 ms 15096 KB Output is correct
17 Correct 99 ms 15068 KB Output is correct
18 Correct 49 ms 12104 KB Output is correct
19 Correct 109 ms 15680 KB Output is correct
20 Correct 120 ms 15776 KB Output is correct
21 Correct 100 ms 15144 KB Output is correct
22 Correct 105 ms 15028 KB Output is correct
23 Correct 109 ms 15908 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9824 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 11 ms 9720 KB Output is correct
4 Correct 11 ms 9720 KB Output is correct
5 Correct 14 ms 9692 KB Output is correct
6 Correct 12 ms 9864 KB Output is correct
7 Correct 12 ms 9692 KB Output is correct
8 Correct 12 ms 9820 KB Output is correct
9 Correct 15 ms 9976 KB Output is correct
10 Correct 11 ms 9720 KB Output is correct
11 Correct 22 ms 10864 KB Output is correct
12 Correct 43 ms 12024 KB Output is correct
13 Correct 47 ms 13404 KB Output is correct
14 Correct 107 ms 15612 KB Output is correct
15 Correct 116 ms 15776 KB Output is correct
16 Correct 106 ms 15096 KB Output is correct
17 Correct 99 ms 15068 KB Output is correct
18 Correct 49 ms 12104 KB Output is correct
19 Correct 109 ms 15680 KB Output is correct
20 Correct 120 ms 15776 KB Output is correct
21 Correct 100 ms 15144 KB Output is correct
22 Correct 105 ms 15028 KB Output is correct
23 Correct 109 ms 15908 KB Output is correct
24 Correct 12 ms 9720 KB Output is correct
25 Correct 124 ms 10844 KB Output is correct
26 Correct 182 ms 12116 KB Output is correct
27 Correct 1549 ms 13504 KB Output is correct
28 Correct 1307 ms 15696 KB Output is correct
29 Correct 2079 ms 15900 KB Output is correct
30 Correct 1068 ms 15168 KB Output is correct
31 Correct 1004 ms 15044 KB Output is correct
32 Correct 154 ms 12068 KB Output is correct
33 Correct 1297 ms 15696 KB Output is correct
34 Correct 1906 ms 15900 KB Output is correct
35 Correct 1059 ms 15644 KB Output is correct
36 Correct 1006 ms 15436 KB Output is correct
37 Correct 976 ms 16428 KB Output is correct
38 Correct 3763 ms 15652 KB Output is correct