Submission #1177465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177465		qrn	Crocodile's Underground City (IOI11_crocodile)	C++20	0 / 100	0 ms	320 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define ins insert
#define fi first
#define se second

#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt int

const intt mod = 1e9 + 7;
const intt base = 31;
const intt inf = 1e9;
const intt mxN = 1e6 + 5;
const intt l = 21;


intt travel_plan(intt N, intt M, intt R[][2], intt L[], intt K, intt P[]) {
    intt isexit[N+1], D[N+1], used[N+1], deg[N+1], edeg[N+1];
    set<pair<intt,intt>> graph[2 * N+1];
    
    for(intt i = 0; i < N; i++) {
        deg[i] = edeg[i] = isexit[i] = 0;
    }
    
    for(intt i = 0; i < M; i++) {
        ++deg[R[i][0]]; 
        ++deg[R[i][1]];
    }

    // for(intt i = 0; i < M; i++) {
    //     cin >> L[i];
    // }

    // cin >> K;
    for(intt i = 0; i < K; i++) {
        // cin >> P[i];
        isexit[P[i]] = 1;
    }
    
    for(intt i = 0; i < M; i++) {
        intt a = R[i][0], b = R[i][1];
        graph[a].insert({b, L[i]});
        graph[b].insert({a, L[i]});
        if(isexit[a]) ++edeg[b];
        if(isexit[b]) ++edeg[a];
    }

    
    vector<intt> temp;
    for(intt i = 0; i < N; i++) {
        intt fl = 0;
        if(isexit[i]) continue;
        for(auto u : graph[i]) {
            if(isexit[u.fi]) {
                fl = 1;
                break;
            }
        }
        if(!fl) temp.pb(i);
    
    }
    
    for(intt node : temp) {
        for(auto u : graph[node]) {
            graph[u.fi].erase({node, u.se});
        }
    }
    

    auto bfs = [&] () {
        intt node = 0;
        for(intt i = 0; i < N; i++) {
            D[i] = inf;
            used[i] = 0;
        };
    
        D[node] = 0;
        queue<intt> q;
        q.push(node);
        while(not q.empty()) {
            intt cur = q.front();
            q.pop();
            if(used[cur]) continue;
            used[cur] = 1;
        
            for(auto g : graph[cur]) {
                intt u = g.fi, w = g.se;
                if(D[u] > D[cur] + w) {
                    D[u] = D[cur] + w;
                    q.push(u);
                }
            }
        }
    };
    
    bfs();

    
    intt tempp = inf, nod = -1;
    for(intt i = 0; i < N; i++) {
        pair<intt,intt> fif = *graph[i].begin();
        intt nodee = fif.fi;
        if(isexit[i] && !((deg[i] == 1 && edeg[nodee] == 1)) && tempp > D[i]) {
            tempp = min(tempp, D[i]);
            nod = i;
        }
    }

    intt ans = inf; 
    for(intt i = 0; i < N; i++) {
        pair<intt,intt> fif = *graph[i].begin();
        intt nodee = fif.fi;
        if(isexit[i] && !((deg[i] == 1 && edeg[nodee] == 1)) && i != nod) {
            ans = min(ans, D[i]);
        }
    }
    return ans;
}

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