Submission #799738

#	Time	Username	Problem	Language	Result	Execution time	Memory
799738		Liudas	악어의 지하 도시 (IOI11_crocodile)	C++17	0 / 100	1 ms	212 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    vector<int> c(N);
    for(int i = 0; i < M; i++){
        c[R[i][0]]++;
        c[R[i][1]]++;
    }
    //cout << "???" << endl;
    for(int i = 0; i < K; i ++){
        c[P[i]] += 1e9;
    }
    //cout << "??" << endl;
    vector<pair<int, int>> tree[N];
    for(int i = 0; i < M; i ++){
        if((c[R[i][0]] == 2 || c[R[i][1]] == 2) && R[i][1] && R[i][0]) continue;
        tree[R[i][0]].push_back({R[i][1], L[i]});
        tree[R[i][1]].push_back({R[i][0], L[i]});
    }
   // cout << "???" << endl;
    priority_queue<pair<int, int>> que;
    for(int i = 0; i < K; i++){
        que.push({0, P[i]});
    }
    vector<int> dist(N, 1e9);
    while(!que.empty()){
        int a = -que.top().first, b = que.top().second;
        //cout << b << endl;
        que.pop();
        if(dist[b] < a)continue;
        dist[b] = a;
        for(auto [l, r] : tree[b]){
            que.push({-r-a, l});
        }
    }
    for(int i = 0; i < N; i++){
        sort(tree[i].begin(), tree[i].end(), [&](auto a, auto b){return dist[a.first] < dist[b.first];});
    }
    que.push({0, 0});
    vector<int> vis(N, false);
    while(!que.empty()){
        int a = -que.top().first, b = que.top().second;
        que.pop();
        if(vis[b])continue;
        vis[b] = true;
        if(!dist[b])return a;
        bool block = false;
        for(auto [i, j] : tree[b]){
            if(block && !vis[i]){
                que.push({-j-a, i});
            }
            if(!vis[i]){
                block = true;
            }
        }
    }
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:5:20: warning: control reaches end of non-void function [-Wreturn-type]
    5 |     vector<int> c(N);
      |                    ^

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11