oj.uz

Submission #900523

# Submission time Handle Problem Language Result Execution time Memory
900523 2024-01-08T12:29:38 Z JakobZorz Tropical Garden (IOI11_garden) C++17
49 / 100
 5000 ms 4188 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
vector<vector<int>>nodes; // lowest node and second lowest node
vector<int>nxt;

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;
    }
}

void count_routes(int N,int M,int P,int R[][2],int Q,int G[]){
    n=N;
    m=M;
    nodes=vector<vector<int>>(n,{-1,-1});
    nxt.resize(2*n);
    for(int i=0;i<m;i++){
        add_conn(R[i][0],R[i][1]);
        add_conn(R[i][1],R[i][0]);
    }
    
    for(int i=0;i<2*n;i++){
        nxt[i]=2*nodes[i/2][i%2];
        if(nodes[nxt[i]/2][0]==i/2&&nodes[nxt[i]/2][1]!=-1)
            nxt[i]++;
    }
    
    for(int i=0;i<Q;i++){
        int res=0;
        for(int j=0;j<n;j++){
            int curr=2*j;
            for(int k=0;k<G[i];k++)
                curr=nxt[curr];
            if(curr/2==P)
                res++;
        }
        answer(res);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 2 ms 604 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Execution timed out 5057 ms 4188 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Execution timed out 5057 ms 4188 KB Time limit exceeded
12 Halted 0 ms 0 KB -