Submission #166096

#	Time	Username	Problem	Language	Result	Execution time	Memory
166096		DavidDamian	Tropical Garden (IOI11_garden)	C++11	100 / 100	2889 ms	36784 KiB

garden

#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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31