Submission #165979

#	Time	Username	Problem	Language	Result	Execution time	Memory
165979		DavidDamian	Tropical Garden (IOI11_garden)	C++11	49 / 100	179 ms	81380 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<vector>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
///Directed Graph
///Determine the number of nodes that can follow a path and finish in P
///Duplicate all the nodes
struct edge
{
    int to;
    int w;
};
bool byW(edge e1,edge e2)
{
    return e1.w<e2.w;
}
vector<edge> graph[250001]; //Given graph
vector<int> adjList[500005]; //Directed graph with duplicated nodes
vector<int> revGraph[500005]; //Reversed graph of the directed graph
void buildGraph(int N) ///Builds a directed graph with the given graph
{
    ///Real node uses its principal edge
    ///Duplicated node uses its secondary edge
    for(int u=0;u<N;u++){
        edge e=graph[u][0]; //Principal edge
        int v=e.to;
        if(graph[v][0].to!=u || graph[v].size()==1){ //Not principal edge of v or v has only one edge
            adjList[u].push_back(v); //Connect with real node
        }
        else{
            adjList[u].push_back(v+N); //Connect with duplicated node
        }
        e=graph[u][1]; //Secondary edge
        v=e.to;
        if(graph[v][0].to!=u || graph[v].size()==1){ //Not principal edge of v or v has only one edge
            adjList[u+N].push_back(v); //Connect with real node
        }
        else{
            adjList[u+N].push_back(v+N); //Connect with duplicated node
        }
    }
}
void Reverse(int N)
{
    for(int u=0;u<2*N;u++){
        if(adjList[u].size()==0) continue;
        int v=adjList[u][0];
        revGraph[v].push_back(u);
    }
}
queue<int> q;
int d[500005][2]; //Distance from P and P+N
int color[500005];
int cycle_size=0;
int inCycle[3]; //P and P+N
void BFS(int s,int op,int P,int N)
{
    d[s][op]=0;
    color[s]=op;
    q.push(s);
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int v: revGraph[u]){
            if(color[v]!=op){
                q.push(v);
                d[v][op]=d[u][op]+1;
            }
            else{ //There is a cycle
                cycle_size=d[u][op]+1;
                if(s==P) inCycle[0]=1;
                if(s==P+N) inCycle[1]=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];
        edge e={v,i};
        graph[u].push_back(e);
        e.to=u;
        graph[v].push_back(e);
    }
    for(int u=0;u<N;u++){
        sort(graph[u].begin(),graph[u].end(),byW); //We get the principal edge in [0] and secondary edge in [1]
    }
    buildGraph(N);
    Reverse(N);
    for(int u=0;u<2*N;u++){
        color[u]=-1;
        d[u][0]=d[u][1]=-1;
    }
    BFS(P,0,P,N); //Computes the distance from all nodes to node P
    BFS(P+N,1,P,N); //Computed the distance from all nodes to node P+N (duplicated node)
    for(int i=0; i<Q; i++){
        int k=G[i];
        int total=0;
        for(int u=0;u<N;u++){
            if(d[u][0]==-1) continue;
            int D=k-d[u][0];
            if(D<0) continue;
            if(D==0){
                total++;
                continue;
            }
            if(inCycle[0]){
                if(cycle_size>0 && D%cycle_size==0) total++;
            }
        }
        for(int u=0;u<N;u++){
            if(d[u][1]==-1) continue;
            int D=k-d[u][1];
            if(D<0) continue;
            if(D==0){
                total++;
                continue;
            }
            if(inCycle[1]){
                if(cycle_size>0 && D%cycle_size==0) total++;
            }
        }
        answer(total);
    }
}

• Subtask 1: 49 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31