oj.uz

Submission #165979

# Submission time Handle Problem Language Result Execution time Memory
165979 2019-11-30T01:38:17 Z DavidDamian Tropical Garden (IOI11_garden) C++11
49 / 100
 179 ms 81380 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 29 ms 29820 KB Output is correct
2 Correct 29 ms 29944 KB Output is correct
3 Correct 29 ms 29944 KB Output is correct
4 Correct 28 ms 29688 KB Output is correct
5 Correct 27 ms 29688 KB Output is correct
6 Correct 31 ms 30044 KB Output is correct
7 Correct 28 ms 29688 KB Output is correct
8 Correct 29 ms 29916 KB Output is correct
9 Correct 32 ms 30148 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 29820 KB Output is correct
2 Correct 29 ms 29944 KB Output is correct
3 Correct 29 ms 29944 KB Output is correct
4 Correct 28 ms 29688 KB Output is correct
5 Correct 27 ms 29688 KB Output is correct
6 Correct 31 ms 30044 KB Output is correct
7 Correct 28 ms 29688 KB Output is correct
8 Correct 29 ms 29916 KB Output is correct
9 Correct 32 ms 30148 KB Output is correct
10 Correct 28 ms 29760 KB Output is correct
11 Correct 48 ms 33516 KB Output is correct
12 Correct 75 ms 36352 KB Output is correct
13 Correct 91 ms 45764 KB Output is correct
14 Runtime error 179 ms 81380 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 29820 KB Output is correct
2 Correct 29 ms 29944 KB Output is correct
3 Correct 29 ms 29944 KB Output is correct
4 Correct 28 ms 29688 KB Output is correct
5 Correct 27 ms 29688 KB Output is correct
6 Correct 31 ms 30044 KB Output is correct
7 Correct 28 ms 29688 KB Output is correct
8 Correct 29 ms 29916 KB Output is correct
9 Correct 32 ms 30148 KB Output is correct
10 Correct 28 ms 29760 KB Output is correct
11 Correct 48 ms 33516 KB Output is correct
12 Correct 75 ms 36352 KB Output is correct
13 Correct 91 ms 45764 KB Output is correct
14 Runtime error 179 ms 81380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -