oj.uz

Submission #7881

# Submission time Handle Problem Language Result Execution time Memory
7881 2014-08-22T14:05:25 Z dohyun0324 Tropical Garden (IOI11_garden) C++
49 / 100
 39 ms 8424 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[150010],q,d[150010][2],leng[150010][2],ch[150010][2],dap[2010];
struct data2{
	int x,p;
}sav[150010];
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 6 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 6 ms 5084 KB Output is correct
5 Correct 6 ms 5076 KB Output is correct
6 Correct 7 ms 5152 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 7 ms 5000 KB Output is correct
9 Correct 10 ms 5340 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 6 ms 5084 KB Output is correct
5 Correct 6 ms 5076 KB Output is correct
6 Correct 7 ms 5152 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 7 ms 5000 KB Output is correct
9 Correct 10 ms 5340 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 18 ms 5936 KB Output is correct
12 Correct 37 ms 6904 KB Output is correct
13 Incorrect 39 ms 8424 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 6 ms 5084 KB Output is correct
5 Correct 6 ms 5076 KB Output is correct
6 Correct 7 ms 5152 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 7 ms 5000 KB Output is correct
9 Correct 10 ms 5340 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 18 ms 5936 KB Output is correct
12 Correct 37 ms 6904 KB Output is correct
13 Incorrect 39 ms 8424 KB Output isn't correct
14 Halted 0 ms 0 KB -