oj.uz

답안 #18629

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18629 2016-02-12T20:41:11 Z ggoh 열대 식물원 (Tropical Garden) (IOI11_garden) C++
49 / 100
 28 ms 5776 KB 
#include "garden.h"
#include "gardenlib.h"
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
#include<vector>
int a,b,c,t,h,p,q,check,p1,q1,y,z,sz1,sz2,v[150003][2],ch[150003][2],x[150003][2],D[150003][2],cycle[150003][2];
void count_routes(int N,int M,int P,int R[][2],int Q,int G[])
{
    a=N;b=M;
    c=P+1;
    for(int i=0;i<b;i++)
    {
        if(x[R[i][0]+1][0]==0)x[R[i][0]+1][0]=R[i][1]+1;
        else if(x[R[i][0]+1][1]==0)x[R[i][0]+1][1]=R[i][1]+1;
        if(x[R[i][1]+1][0]==0)x[R[i][1]+1][0]=R[i][0]+1;
        else if(x[R[i][1]+1][1]==0)x[R[i][1]+1][1]=R[i][0]+1;
    }
    for(int i=1;i<=a;i++)
    {
        if(x[i][1]==0)x[i][1]=x[i][0];
    }
    p=c;q=0;t=0;
    D[p][q]=0;
    ch[p][q]=1;

    v[p][q]=1;
    p1=-1;q1=-1;
    while(1)
    {
        if(q==0)p1=x[p][0];
        else p1=x[p][1];
        if(p==x[p1][0])q1=1;
        else q1=0;
        if(p1==c&&q1==0)break;
        else
        {
            if(v[p1][q1]==1)break;
            v[p1][q1]=1;
            p=p1;q=q1;
            t++;
        }
    }
    if(p1==c&&q1==0)
    {
        p=c;q=0;
        cycle[p][q]=t+1;
        while(1)
        {
            if(q==0)p1=x[p][0];
            else p1=x[p][1];
            if(p==x[p1][0])q1=1;
            else q1=0;
            if(p1==c&&q1==0)break;
            p=p1;q=q1;
            ch[p][q]=1;
            D[p][q]=t;t--;
            cycle[p][q]=cycle[c][0];
        }
    }
    memset(v,0,sizeof(v));

    p=c;q=1;t=0;
    D[p][q]=0;
    ch[p][q]=1;

    v[p][q]=1;
    p1=-1;q1=-1;
    while(1)
    {
        if(q==0)p1=x[p][0];
        else p1=x[p][1];
        if(p==x[p1][0])q1=1;
        else q1=0;
        if(p1==c&&q1==1)break;
        else
        {
            if(v[p1][q1]==1)break;
            v[p1][q1]=1;
            p=p1;q=q1;
            t++;
        }
    }
    if(p1==c&&q1==1)
    {
        p=c;q=1;
        cycle[p][q]=t+1;
        while(1)
        {
            if(q==0)p1=x[p][0];
            else p1=x[p][1];
            if(p==x[p1][0])q1=1;
            else q1=0;
            if(p1==c&&q1==1)break;
            p=p1;q=q1;
            if(ch[p][q]==0){
            ch[p][q]=1;
            D[p][q]=t;
            }
            else if(D[p][q]>t)
            {
                D[p][q]=t;
            }
            cycle[p][q]=cycle[c][1];
            t--;
        }
    }

    memset(v,0,sizeof(v));
    for(int i=1;i<=a;i++)
    {
        for(int j=0;j<2;j++)
        {
            if(ch[i][j])continue;
            p=i;q=j;t=0;
            v[i][j]=1;
            while(1)
            {
                if(q==0)p1=x[p][0];
                else p1=x[p][1];
                if(p==x[p1][0])q1=1;
                else q1=0;
                t++;
                if(ch[p1][q1])break;
                else if(v[p1][q1])break;
                p=p1;q=q1;
                v[p][q]=1;
            }
            if(ch[p1][q1])
            {
                y=p1;z=q1;
                p=i;q=j;
                ch[p][q]=1;
                D[p][q]=D[y][z]+t;
                cycle[p][q]=cycle[y][z];
                while(1)
                {
                    if(q==0)p1=x[p][0];
                    else p1=x[p][1];
                    if(p==x[p1][0])q1=1;
                    else q1=0;
                    t--;
                    if(p1==y&&q1==z)break;
                    p=p1;q=q1;
                    ch[p][q]=1;
                    D[p][q]=D[y][z]+t;
                    cycle[p][q]=cycle[y][z];
                }
            }
        }
    }
    int ans;
    for(int i=0;i<Q;i++)
    {
        ans=0;
        for(int j=1;j<=a;j++)
        {
            if(ch[j][0]&&(D[j][0]==G[i]||(cycle[j][0]&&G[i]>D[j][0]&&(G[i]-D[j][0])%cycle[j][0]==0)))
            {
                ans++;
            }
        }
        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1500 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1504 KB Output is correct
5 Correct 3 ms 1504 KB Output is correct
6 Correct 3 ms 1512 KB Output is correct
7 Correct 3 ms 1508 KB Output is correct
8 Correct 3 ms 1548 KB Output is correct
9 Correct 5 ms 1648 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1500 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1504 KB Output is correct
5 Correct 3 ms 1504 KB Output is correct
6 Correct 3 ms 1512 KB Output is correct
7 Correct 3 ms 1508 KB Output is correct
8 Correct 3 ms 1548 KB Output is correct
9 Correct 5 ms 1648 KB Output is correct
10 Correct 3 ms 1500 KB Output is correct
11 Correct 9 ms 2384 KB Output is correct
12 Correct 18 ms 3496 KB Output is correct
13 Incorrect 28 ms 5776 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1500 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1504 KB Output is correct
5 Correct 3 ms 1504 KB Output is correct
6 Correct 3 ms 1512 KB Output is correct
7 Correct 3 ms 1508 KB Output is correct
8 Correct 3 ms 1548 KB Output is correct
9 Correct 5 ms 1648 KB Output is correct
10 Correct 3 ms 1500 KB Output is correct
11 Correct 9 ms 2384 KB Output is correct
12 Correct 18 ms 3496 KB Output is correct
13 Incorrect 28 ms 5776 KB Output isn't correct
14 Halted 0 ms 0 KB -