oj.uz

답안 #7881

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

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

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

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