oj.uz

Submission #1009830

# Submission time Handle Problem Language Result Execution time Memory
1009830 2024-06-28T06:26:59 Z Mardonbekhazratov Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 2 ms 4696 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;

vector<int>ans;
vector<bool>is,vis;
vector<vector<pair<int,int>>>v;

const int INF=1e9;

void dfs(int x,int p=-1){
    vis[x]=true;
    if(is[x]){
        ans[x]=0;
        return;
    }
    vector<ll>a={INF,INF};
    for(auto [z,w]:v[x]){
        if(!vis[z]){
            dfs(z,x);
        }
        if(z!=p) a.push_back(w+ans[z]);
    }
    sort(a.begin(),a.end());
    ans[x]=a[1];
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    is.assign(N,false);
    vis.assign(N,false);
    for(int i=0;i<K;i++) is[P[i]]=true;
    v.resize(N);
    ans.assign(N,false);
    for(int i=0;i<M;i++){
        v[R[i][0]].push_back({R[i][1],L[i]});
        v[R[i][1]].push_back({R[i][0],L[i]});
    }
    dfs(0);
    return ans[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2504 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2504 KB Output is correct
9 Incorrect 2 ms 2652 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2504 KB Output is correct
9 Incorrect 2 ms 2652 KB Output isn't correct
10 Halted 0 ms 0 KB -