oj.uz

Submission #900393

# Submission time Handle Problem Language Result Execution time Memory
900393 2024-01-08T08:23:31 Z JakobZorz Tropical Garden (IOI11_garden) C++17
0 / 100
 0 ms 348 KB 
#include"garden.h"
#include"gardenlib.h"
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

int n; // num nodes
int m; // num edges
int p; // destination
vector<vector<int>>nodes; // lowest node and second lowest node
vector<vector<int>>dist;

void add_conn(int node,int dest){
    if(nodes[node][0]==-1){
        nodes[node]={dest,dest};
    }else if(nodes[node][0]==nodes[node][1]){
        nodes[node][1]=dest;
    }
}

int dfs(int node,int blocked){
    if(dist[node][blocked]!=-1)
        return dist[node][blocked];
    dist[node][blocked]=1e9;
    int blocked2=0;
    int nxt=nodes[node][blocked];
    if(nodes[nxt][0]==node&&nodes[nxt][1]!=-1)
        blocked2=1;
    dist[node][blocked]=dfs(nxt,blocked2)+1;
    return dist[node][blocked];
}

void count_routes(int N,int M,int P,int R[][2],int Q,int G[]){
    n=N;
    m=M;
    p=P;
    nodes=vector<vector<int>>(n,{-1,-1});
    dist=vector<vector<int>>(n,{-1,-1});
    for(int i=0;i<m;i++){
        add_conn(R[i][0],R[i][1]);
        add_conn(R[i][1],R[i][0]);
    }
    dist[p]={0,0};
    
    unordered_map<int,int>mp;
    for(int i=0;i<n;i++){
        mp[dfs(i,0)]++;
    }
    
    for(int i=0;i<Q;i++)
        answer(mp[G[i]]);
}

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -