oj.uz

Submission #165976

# Submission time Handle Problem Language Result Execution time Memory
165976 2019-11-30T01:24:22 Z DavidDamian Tropical Garden (IOI11_garden) C++11
49 / 100
 152 ms 57580 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[150001]; //Given graph
vector<int> adjList[300005]; //Directed graph with duplicated nodes
vector<int> revGraph[300005]; //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[300005][2]; //Distance from P and P+N
int color[300005];
int cycle_size=0;
int inCycle[2]; //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 19 ms 18140 KB Output is correct
2 Correct 18 ms 18168 KB Output is correct
3 Correct 18 ms 18172 KB Output is correct
4 Correct 18 ms 18012 KB Output is correct
5 Correct 17 ms 17912 KB Output is correct
6 Correct 19 ms 18216 KB Output is correct
7 Correct 18 ms 17912 KB Output is correct
8 Correct 19 ms 18140 KB Output is correct
9 Correct 21 ms 18296 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18140 KB Output is correct
2 Correct 18 ms 18168 KB Output is correct
3 Correct 18 ms 18172 KB Output is correct
4 Correct 18 ms 18012 KB Output is correct
5 Correct 17 ms 17912 KB Output is correct
6 Correct 19 ms 18216 KB Output is correct
7 Correct 18 ms 17912 KB Output is correct
8 Correct 19 ms 18140 KB Output is correct
9 Correct 21 ms 18296 KB Output is correct
10 Correct 18 ms 18012 KB Output is correct
11 Correct 36 ms 21752 KB Output is correct
12 Correct 66 ms 24688 KB Output is correct
13 Correct 79 ms 34004 KB Output is correct
14 Runtime error 152 ms 57580 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 19 ms 18140 KB Output is correct
2 Correct 18 ms 18168 KB Output is correct
3 Correct 18 ms 18172 KB Output is correct
4 Correct 18 ms 18012 KB Output is correct
5 Correct 17 ms 17912 KB Output is correct
6 Correct 19 ms 18216 KB Output is correct
7 Correct 18 ms 17912 KB Output is correct
8 Correct 19 ms 18140 KB Output is correct
9 Correct 21 ms 18296 KB Output is correct
10 Correct 18 ms 18012 KB Output is correct
11 Correct 36 ms 21752 KB Output is correct
12 Correct 66 ms 24688 KB Output is correct
13 Correct 79 ms 34004 KB Output is correct
14 Runtime error 152 ms 57580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -