oj.uz

Submission #166096

# Submission time Handle Problem Language Result Execution time Memory
166096 2019-11-30T16:42:08 Z DavidDamian Tropical Garden (IOI11_garden) C++11
100 / 100
 2889 ms 36784 KB 
#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include<vector>
using namespace std;
vector<int> adjList[300005];
vector<int> original[150005];
short vis[300005];
void buildGraph(int N)
{
    for(int u=0;u<N;u++){
        int v=original[u][0]; //Principal edge
        if(original[v][0]!=u || original[v].size()==1){
            adjList[v].push_back(u);
        }
        else{
            adjList[v+N].push_back(u);
        }
        if(original[u].size()==1) continue;
        v=original[u][1]; //Secondary edge
        if(original[v][0]!=u || original[v].size()==1){
            adjList[v].push_back(u+N);
        }
        else{
            adjList[v+N].push_back(u+N);
        }
    }
}
int color[300005];
int d[300005][2];
int C[2]={-1,-1}; //Cycle Size
int inCycle[2];
int t=0;
void dfs(int u)
{
    color[u]=1;
    for(int v: adjList[u]){
        if(color[v]==0){
            d[v][t]=d[u][t]+1;
            dfs(v);
        }
        else if(color[v]==1){
            C[t]=d[u][t]+1;
            inCycle[t]=1;
        }
    }
    color[u]=-1;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    for(int i=0;i<M;i++){
        int u=R[i][0];
        int v=R[i][1];
        original[u].push_back(v);
        original[v].push_back(u);
    }
    buildGraph(N);
    for(int i=0;i<2*N;i++){
        d[i][0]=d[i][1]=1000000000;
    }
    d[P][0]=0;
    dfs(P);
    t++;
    for(int i=0;i<2*N;i++){
        color[i]=0;
    }
    d[P+N][1]=0;
    dfs(P+N);
    /*for(int i=0;i<2*N;i++){
        cout<<d[i][0]<<" "<<d[i][1]<<endl;
    }*/
    //cout<<inCycle[0]<<" "<<C[0]<<endl;
    //cout<<inCycle[1]<<" "<<C[1]<<endl;
    for(int i=0;i<Q;i++){
        int k=G[i];
        int total=0;
        for(int u=0;u<N;u++){
            for(int j=0;j<2;j++){
                if(d[u][j]==1000000000) continue; //Not reachable
                if(inCycle[j]){
                    int D=k-d[u][j];
                    if(D>=0){
                        if(D%C[j]==0) total++;
                    }
                }
                else{
                    int D=k-d[u][j]; //Distance is exactly the same
                    if(D==0) total++;
                }
            }
        }
        answer(total);
    }

}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11132 KB Output is correct
2 Correct 12 ms 11100 KB Output is correct
3 Correct 12 ms 11084 KB Output is correct
4 Correct 11 ms 10872 KB Output is correct
5 Correct 11 ms 10872 KB Output is correct
6 Correct 12 ms 11128 KB Output is correct
7 Correct 11 ms 10872 KB Output is correct
8 Correct 11 ms 10972 KB Output is correct
9 Correct 14 ms 11188 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11132 KB Output is correct
2 Correct 12 ms 11100 KB Output is correct
3 Correct 12 ms 11084 KB Output is correct
4 Correct 11 ms 10872 KB Output is correct
5 Correct 11 ms 10872 KB Output is correct
6 Correct 12 ms 11128 KB Output is correct
7 Correct 11 ms 10872 KB Output is correct
8 Correct 11 ms 10972 KB Output is correct
9 Correct 14 ms 11188 KB Output is correct
10 Correct 11 ms 10872 KB Output is correct
11 Correct 25 ms 13280 KB Output is correct
12 Correct 47 ms 14776 KB Output is correct
13 Correct 70 ms 29628 KB Output is correct
14 Correct 165 ms 24056 KB Output is correct
15 Correct 204 ms 24296 KB Output is correct
16 Correct 162 ms 20784 KB Output is correct
17 Correct 157 ms 19488 KB Output is correct
18 Correct 48 ms 14828 KB Output is correct
19 Correct 154 ms 23972 KB Output is correct
20 Correct 195 ms 24308 KB Output is correct
21 Correct 155 ms 20656 KB Output is correct
22 Correct 139 ms 19392 KB Output is correct
23 Correct 167 ms 25360 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11132 KB Output is correct
2 Correct 12 ms 11100 KB Output is correct
3 Correct 12 ms 11084 KB Output is correct
4 Correct 11 ms 10872 KB Output is correct
5 Correct 11 ms 10872 KB Output is correct
6 Correct 12 ms 11128 KB Output is correct
7 Correct 11 ms 10872 KB Output is correct
8 Correct 11 ms 10972 KB Output is correct
9 Correct 14 ms 11188 KB Output is correct
10 Correct 11 ms 10872 KB Output is correct
11 Correct 25 ms 13280 KB Output is correct
12 Correct 47 ms 14776 KB Output is correct
13 Correct 70 ms 29628 KB Output is correct
14 Correct 165 ms 24056 KB Output is correct
15 Correct 204 ms 24296 KB Output is correct
16 Correct 162 ms 20784 KB Output is correct
17 Correct 157 ms 19488 KB Output is correct
18 Correct 48 ms 14828 KB Output is correct
19 Correct 154 ms 23972 KB Output is correct
20 Correct 195 ms 24308 KB Output is correct
21 Correct 155 ms 20656 KB Output is correct
22 Correct 139 ms 19392 KB Output is correct
23 Correct 167 ms 25360 KB Output is correct
24 Correct 13 ms 10952 KB Output is correct
25 Correct 159 ms 13368 KB Output is correct
26 Correct 228 ms 14892 KB Output is correct
27 Correct 1656 ms 29632 KB Output is correct
28 Correct 1652 ms 24064 KB Output is correct
29 Correct 1804 ms 24312 KB Output is correct
30 Correct 1141 ms 20796 KB Output is correct
31 Correct 1115 ms 19484 KB Output is correct
32 Correct 286 ms 14940 KB Output is correct
33 Correct 1709 ms 24060 KB Output is correct
34 Correct 1719 ms 24300 KB Output is correct
35 Correct 1142 ms 20684 KB Output is correct
36 Correct 1693 ms 19496 KB Output is correct
37 Correct 1396 ms 25360 KB Output is correct
38 Correct 2889 ms 36784 KB Output is correct