Submission #1218532

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

crocodile

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <complex>
#include <list>
#include <cassert>
#include <chrono>
#include <random>
#include <stack>
#include <iomanip>
#include <fstream>
using namespace std;

#define endl "\n"
// #define int long long

const int INF = 1e9+7;
const int MOD = 1e9+7;

set<int> last;
vector<vector<pair<int, int>>> adj;

int best1 = INF, best2 = INF;

void dfs(int u, int p, int curr){
    for(auto &[v, w] : adj[u]){
        if(v == p) continue;
        int next = curr+w;
        if(last.find(v) != last.end()){
            if(next < best1){
                swap(best1, best2);
                best1 = next;
            } else if(next < best2){
                best2 = next;
            }
        }
        dfs(v, u, next);
    }
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
    adj.resize(n+1);
    for(int i = 0; i < m; i++){
        adj[r[i][0]].push_back({r[i][1], l[i]});
    }
    for(int i = 0; i < k; i++) last.insert(p[i]);

    // for(int i = 0; i < n; i++){
    //     cout << i << " -> ";
    //     for(auto &j : adj[i]){
    //         cout << j.first << " " << j.second << " | ";
    //     }
    //     cout << endl;
    // }

    dfs(0, -1, 0);

    return best2;

    // cout << best2 << endl;

    // return 0;
}

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