Submission #878977

#	Time	Username	Problem	Language	Result	Execution time	Memory
878977		AverageAmogusEnjoyer	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	541 ms	63828 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,1:0; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,1:0; }
const int N=1e5;
vector<pair<int,int>> adj[N];
int dist[N][2];
int travel_plan(int n, int m, int edges[][2], int t[], int k, int exits[]) {
    for (int i=0;i<m;i++) {
        adj[edges[i][0]].emplace_back(edges[i][1],t[i]);
        adj[edges[i][1]].emplace_back(edges[i][0],t[i]);
    }
    set<pair<int,int>> q;
    memset(dist,0x3f,sizeof(dist));
    for (int i=0;i<k;i++) {
        dist[exits[i]][0]=dist[exits[i]][1]=0;
        q.insert(make_pair(0,exits[i]));
    }
    while(!q.empty()) {
        int u=(*q.begin()).second; 
        int d=dist[u][1]; 
        q.erase(q.begin());
        for (auto &[v,len]: adj[u]) {
            assert(dist[v][0]<=dist[v][1]);
            if (d+len<dist[v][0]) {
                q.erase(make_pair(dist[v][1],v));
                dist[v][1]=dist[v][0];
                dist[v][0]=d+len;
                q.insert(make_pair(dist[v][1],v));
            } else if (d+len<dist[v][1]) {
                q.erase(make_pair(dist[v][1],v));
                dist[v][1]=d+len;
                q.insert(make_pair(dist[v][1],v));
            }
        }
    }
    return dist[0][1];
}   
/*
int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    int n,m,k; cin >> n >> m >> k;
    int edges[m][2],t[m],exits[k];
    for (int i=0;i<m;i++) {
        cin >> edges[i][0] >> edges[i][1] >> t[i];
    }
    for (int i=0;i<k;i++) {
        cin >> exits[i];
    }
    int res; cin >> res;
    assert(res==travel_plan(n,m,edges,t,k,exits));
}
*/

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