oj.uz

Submission #165977

# Submission time Handle Problem Language Result Execution time Memory
165977 2019-11-30T01:26:36 Z DavidDamian Tropical Garden (IOI11_garden) C++11
49 / 100
 172 ms 81336 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(D>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(D%cycle_size==0) total++;
            }
        }
        answer(total);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 29816 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 29716 KB Output is correct
5 Correct 29 ms 29688 KB Output is correct
6 Correct 30 ms 29900 KB Output is correct
7 Correct 29 ms 29776 KB Output is correct
8 Correct 30 ms 29816 KB Output is correct
9 Correct 32 ms 30092 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 29816 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 29716 KB Output is correct
5 Correct 29 ms 29688 KB Output is correct
6 Correct 30 ms 29900 KB Output is correct
7 Correct 29 ms 29776 KB Output is correct
8 Correct 30 ms 29816 KB Output is correct
9 Correct 32 ms 30092 KB Output is correct
10 Correct 29 ms 29660 KB Output is correct
11 Correct 46 ms 33532 KB Output is correct
12 Correct 74 ms 36384 KB Output is correct
13 Correct 89 ms 45688 KB Output is correct
14 Runtime error 172 ms 81336 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 29 ms 29816 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 29716 KB Output is correct
5 Correct 29 ms 29688 KB Output is correct
6 Correct 30 ms 29900 KB Output is correct
7 Correct 29 ms 29776 KB Output is correct
8 Correct 30 ms 29816 KB Output is correct
9 Correct 32 ms 30092 KB Output is correct
10 Correct 29 ms 29660 KB Output is correct
11 Correct 46 ms 33532 KB Output is correct
12 Correct 74 ms 36384 KB Output is correct
13 Correct 89 ms 45688 KB Output is correct
14 Runtime error 172 ms 81336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -