Submission #166097

#	Time	Username	Problem	Language	Result	Execution time	Memory
166097		DavidDamian	Tropical Garden (IOI11_garden)	C++11	100 / 100	2896 ms	36792 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include<vector>
using namespace std;
///Duplicate nodes
///Directed graph
///Determine the number of nodes that can follow a path and end in P in exactly K steps
vector<int> adjList[300005];
vector<int> original[150005];
short vis[300005];
void buildGraph(int N) ///Creates duplicated and reversed graph 
{
  	///Real node uses its prncipal edge
  	///Duplicated node uses its secondary edge
    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) ///Computes distance from P and P+N (duplicated node) to all nodes
{
    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){ //P/P+N is on a cycle
            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<Q;i++){ //For each query
        int k=G[i];
        int total=0;
        for(int u=0;u<N;u++){ //For each node
            for(int j=0;j<2;j++){ //Checks if the distance is 0 modulo C
                if(d[u][j]==1000000000) continue; //Not reachable
                if(inCycle[j]){ //Cycle
                    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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31