제출 #1273495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273495		zuz14	악어의 지하 도시 (IOI11_crocodile)	C++20	100 / 100	616 ms	75632 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
#define F first
#define S second
using namespace std;
    
vector<pair<int, int>> g[100007];
int times[100007], under[100007];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
    priority_queue<pair<long long, int>> q;
    int dist;
    int v;

    for (int i=0; i<m; i++) {g[r[i][0]].push_back({l[i], r[i][1]}); g[r[i][1]].push_back({l[i], r[i][0]});}
    for (int i=0; i<n; i++) times[i]=-1;
    
    for (int i=0; i<k; i++) q.push({0, p[i]}); 

    while (!q.empty()){
        dist=-q.top().F, v=q.top().S; q.pop();

        //cout<<v<<' '<<dist<<endl;
        
        if (times[v]!=-1) continue;
        if (under[v]<1 && dist>0) {under[v]++; continue;}
        times[v]=dist;
        //cout<<"v "<<v<<' '<<under[v]<<endl;

        for (auto i:g[v]) {q.push({-dist-i.F, i.S}); /*cout<<i.S<<endl;*/}
    }

    return times[0];
}

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