oj.uz

Submission #7513

# Submission time Handle Problem Language Result Execution time Memory
7513 2014-08-10T07:41:42 Z Namnamseo Tropical Garden (IOI11_garden) C++
100 / 100
 2786 ms 12136 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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