답안 #7513 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
7513	2014-08-10T07:41:42 Z	Namnamseo	열대 식물원 (Tropical Garden) (IOI11_garden)	C++	100 / 100	2786 ms	12136 KB

garden

#include "garden.h"
#include "gardenlib.h"

int befnext[150010][2];

int next[300010];
int nc  [300010];

int p;

void addEdge(int a,int b)
{
    if(nc[a]<2)
    {
        befnext[a][nc[a]]=b;
        nc[a]++;
    }
    if(nc[b]<2)
    {
        befnext[b][nc[b]]=a;
        nc[b]++;
    }
}

int visit  [300010];
int dists  [300010];

int pdist  [300010][2];
int loops  [300010][2];

int vn;

int stack [300010];

void run(int pos)
{
    int bef=-1;

    int metpdist[2]= {-1,-1};

    int top = 0;
    int loopsize;
    int temp;
    while(true)
    {
        if(visit[pos]==vn)
        {
            loopsize = dists[bef] - dists[pos] + 1;

            int top_orig = top;
            int i;
            for(i=0; i<2; i++)
            {
                if(metpdist[i]!=-1)
                {
                    if(metpdist[i]>=dists[pos])
                    {
                        // p[i] is in the graph
                        temp = (metpdist[i]-dists[pos]+1)%loopsize;
                        top = top_orig;
                        while(top!=0)
                        {
                            if(stack[top-1] == p + 150000*i) temp%=loopsize;
                            loops[stack[top-1]][i]=loopsize;
                            pdist[stack[top-1]][i]=temp;
                            temp++;
                            top--;
                        }
                    }
                    else
                    {
                        while(top!=0)
                        {
                            if(metpdist[i] == dists[stack[top-1]]) break;
                            top--;
                        }
                        temp = 0;
                        while(top!=0)
                        {
                            pdist[stack[top-1]][i] = temp;
                            loops[stack[top-1]][i] = 987654321;
                            temp++;
                            top--;
                        }
                    }
                }
            }
            break;
        }
        if(visit[pos]!=-1 && visit[pos]<vn)
        {
            int i,l;
            int origtop = top;
            for(i=0; i<2; i++)
            {
                if(pdist[pos][i]==-1) {
                    if(metpdist[i] != -1){
                        top = origtop;
                        while(top != 0){
                            if(stack[top-1] == p + 150000*i){
                                break;
                            }
                            top--;
                        }
                        temp=0;
                        while(top!=0){
                            loops[stack[top-1]][i]=987654321;
                            pdist[stack[top-1]][i]=temp;
                            temp++;
                            top--;
                        }
                    }
                    continue;
                }
                l=loops[pos][i];
                temp = pdist[pos][i]+1;
                top = origtop;
                while(top!=0)
                {
                    pdist[stack[top-1]][i]=temp;
                    loops[stack[top-1]][i]=l;
                    temp++;
                    top--;
                }
            }
            
            break;
        }
 
 
        if(bef!=-1) dists[pos] = dists[bef] + 1;
        else dists[pos]=0;
 
 
 
        if(pos == p)
        {
            metpdist[0] = dists[pos];
        }
        else if(pos==p+150000)
        {
            metpdist[1] = dists[pos];
        }
 
        stack[top++]=pos;
        visit[pos]=vn;
 
        bef=pos;
        pos = next[pos];
    }
    vn++;
}
 
void findP(int n,int steps)
{
    int i,j;
    int ans=0;
    for(i=0; i<n; i++)
    {
        for(j=0; j<2; j++)
        {
            if(pdist[i][j]!=-1)
            {
                
                if(loops[i][j] == 987654321)
                {
                    if(pdist[i][j]==steps)
                    {
                        ans++;
                        break;
                    }
                    continue;
                }
                if(steps>=pdist[i][j] && !((steps-pdist[i][j])%loops[i][j]))
                {
                    ans++;
                    break;
                }
            }
        }
    }
    answer(ans);
}
 
void count_routes(int n, int m, int P, int R[][2], int Q, int G[])
{
    p=P;
    int i;
    int a,b;
    for(i=0; i<m; i++)
    {
        a=R[i][0];
        b=R[i][1];
        addEdge(a,b);
    }
    for(i=0; i<n; i++)
    {
        if(nc[i]>=1)
        {
            next[i]=befnext[i][0];
            if(befnext[befnext[i][0]][0]==i)
            {
                next[i]+=150000;
            }
            if(nc[i]==2)
            {
                next[i+150000]=befnext[i][1];
                if(befnext[befnext[i][1]][0]==i)
                {
                    next[i+150000]+=150000;
                }
            }
            else {
                next[i+150000]=next[i];
            }
        }
 
 
        visit[i]=visit[i+150000]=-1;
        
        pdist[i][0]=pdist[i][1]=-1;
        loops[i][0]=loops[i][1]=-1;
        
        pdist[i+150000][0]=pdist[i+150000][1]=-1;
        loops[i+150000][0]=loops[i+150000][1]=-1;
    }
 
    vn=1;
 
    for(i=0; i<n; i++)
    {
        if(visit[i]==-1 && nc[i]) run(i);
        if(visit[i+150000]==-1 && nc[i]) run(i+150000);
    }
 
    for(i=0; i<Q; i++) findP(n,G[i]);
 
 
 
}

Subtask #1
49.0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	476 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	508 KB	Output is correct
9	Correct	4 ms	504 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	476 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	508 KB	Output is correct
9	Correct	4 ms	504 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	9 ms	2040 KB	Output is correct
12	Correct	19 ms	3320 KB	Output is correct
13	Correct	29 ms	7416 KB	Output is correct
14	Correct	59 ms	10460 KB	Output is correct
15	Correct	67 ms	10636 KB	Output is correct
16	Correct	51 ms	7544 KB	Output is correct
17	Correct	48 ms	6528 KB	Output is correct
18	Correct	19 ms	3292 KB	Output is correct
19	Correct	59 ms	10512 KB	Output is correct
20	Correct	66 ms	10664 KB	Output is correct
21	Correct	53 ms	7588 KB	Output is correct
22	Correct	49 ms	6580 KB	Output is correct
23	Correct	61 ms	11488 KB	Output is correct

Subtask #3
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	476 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	508 KB	Output is correct
9	Correct	4 ms	504 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	9 ms	2040 KB	Output is correct
12	Correct	19 ms	3320 KB	Output is correct
13	Correct	29 ms	7416 KB	Output is correct
14	Correct	59 ms	10460 KB	Output is correct
15	Correct	67 ms	10636 KB	Output is correct
16	Correct	51 ms	7544 KB	Output is correct
17	Correct	48 ms	6528 KB	Output is correct
18	Correct	19 ms	3292 KB	Output is correct
19	Correct	59 ms	10512 KB	Output is correct
20	Correct	66 ms	10664 KB	Output is correct
21	Correct	53 ms	7588 KB	Output is correct
22	Correct	49 ms	6580 KB	Output is correct
23	Correct	61 ms	11488 KB	Output is correct
24	Correct	3 ms	376 KB	Output is correct
25	Correct	92 ms	2140 KB	Output is correct
26	Correct	122 ms	3292 KB	Output is correct
27	Correct	1682 ms	7436 KB	Output is correct
28	Correct	1162 ms	10540 KB	Output is correct
29	Correct	1813 ms	10672 KB	Output is correct
30	Correct	962 ms	7600 KB	Output is correct
31	Correct	1193 ms	6620 KB	Output is correct
32	Correct	134 ms	3320 KB	Output is correct
33	Correct	1168 ms	10524 KB	Output is correct
34	Correct	1718 ms	10676 KB	Output is correct
35	Correct	950 ms	7592 KB	Output is correct
36	Correct	1765 ms	6608 KB	Output is correct
37	Correct	800 ms	11448 KB	Output is correct
38	Correct	2786 ms	12136 KB	Output is correct

답안 #7513

Compilation message

Subtask #1 49.0 / 49.0

Subtask #2 20.0 / 20.0

Subtask #3 31.0 / 31.0

Subtask #1
49.0 / 49.0

Subtask #2
20.0 / 20.0

Subtask #3
31.0 / 31.0