oj.uz

Submission #165978

# Submission time Handle Problem Language Result Execution time Memory
165978 2019-11-30T01:31:04 Z DavidDamian Tropical Garden (IOI11_garden) C++11
49 / 100
 173 ms 81404 KB 
#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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 29824 KB Output is correct
2 Correct 29 ms 29816 KB Output is correct
3 Correct 29 ms 29944 KB Output is correct
4 Correct 28 ms 29660 KB Output is correct
5 Correct 28 ms 29736 KB Output is correct
6 Correct 29 ms 29944 KB Output is correct
7 Correct 28 ms 29772 KB Output is correct
8 Correct 29 ms 29876 KB Output is correct
9 Correct 32 ms 30044 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 29824 KB Output is correct
2 Correct 29 ms 29816 KB Output is correct
3 Correct 29 ms 29944 KB Output is correct
4 Correct 28 ms 29660 KB Output is correct
5 Correct 28 ms 29736 KB Output is correct
6 Correct 29 ms 29944 KB Output is correct
7 Correct 28 ms 29772 KB Output is correct
8 Correct 29 ms 29876 KB Output is correct
9 Correct 32 ms 30044 KB Output is correct
10 Correct 28 ms 29688 KB Output is correct
11 Correct 47 ms 33628 KB Output is correct
12 Correct 74 ms 36400 KB Output is correct
13 Correct 94 ms 45756 KB Output is correct
14 Runtime error 173 ms 81404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 29824 KB Output is correct
2 Correct 29 ms 29816 KB Output is correct
3 Correct 29 ms 29944 KB Output is correct
4 Correct 28 ms 29660 KB Output is correct
5 Correct 28 ms 29736 KB Output is correct
6 Correct 29 ms 29944 KB Output is correct
7 Correct 28 ms 29772 KB Output is correct
8 Correct 29 ms 29876 KB Output is correct
9 Correct 32 ms 30044 KB Output is correct
10 Correct 28 ms 29688 KB Output is correct
11 Correct 47 ms 33628 KB Output is correct
12 Correct 74 ms 36400 KB Output is correct
13 Correct 94 ms 45756 KB Output is correct
14 Runtime error 173 ms 81404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -