Submission #924204

#	Time	Username	Problem	Language	Result	Execution time	Memory
924204		Karoot	Evacuation plan (IZhO18_plan)	C++17	100 / 100	775 ms	70324 KiB

plan

#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;

ll linf = 1e15+1;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

int n, m;
const int MAXN = 1e5+1; //M <= 5e5+1 dock

vector<pair<int, int> > adj[MAXN];
int weight[MAXN];

vector<int> edgesMST[MAXN];
int binPar[MAXN][20];
int binWeight[MAXN][20];
bool isVisited[MAXN];
bool active[MAXN];
int depth[MAXN];

void initBin(){
    for (int j = 1; j < 20; j++){
        for (int i = 0; i < n; i++){
            binPar[i][j] = binPar[binPar[i][j-1]][j-1];
            binWeight[i][j] = min(binWeight[i][j-1], binWeight[binPar[i][j-1]][j-1]);
        }
    }
}

int jump(int x, int k){
    for (int i = 19; i >= 0; i--){
        if (k&(1<<i))x = binPar[x][i];
    }
    return x;
}


int lca(int a, int b){
    if (depth[a] < depth[b])swap(a, b);
    a = jump(a, depth[a]-depth[b]);
    if (a == b)return a;
    for (int i = 19; i >= 0; i--){
        int aT = binPar[a][i], bT = binPar[b][i];
        if (aT != bT){
            a = aT;
            b = bT;
        }
    }
    return binPar[a][0];
}

int getMin(int node, int k){
    int mini = weight[node];
    for (int i = 19; i >= 0; i--){
        if (k&(1<<i)){
            mini = min(mini, binWeight[node][i]);
            node = binPar[node][i];
            //cout << "; " << i << " " << binWeight[node][i] << endl;
        }
    }
    return mini;
}

int main(){
    scoobydoobydoo();
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int a, b, w; cin >> a >> b >> w;
        a--; b--;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    
    int k; cin >> k;
    vector<int> NPP(k);
    priority_queue<pair<int, int> > pq;
    for (int i = 0; i < k; i++){
        cin >> NPP[i];
        pq.push({0, --NPP[i]});
    }

    int maxi = -1;
    int best;

    while (!pq.empty()){
        int node = pq.top().second;
        int w = -pq.top().first;
        pq.pop();
        if (isVisited[node])continue;
        isVisited[node] = true;
        weight[node] = w;
        if (weight[node] > maxi){
            maxi = w;
            best = node;
        }
        for (auto p : adj[node]){
            if (!isVisited[p.first])pq.push({-(w+p.second), p.first});
        }
    }

    active[best] = true;


    priority_queue<vector<int> > sPq;

    for (auto p : adj[best]){
        sPq.push({weight[best], p.first, best, 1});
    }

    depth[best] = 0;

    binPar[best][0] = best;
    
    while (!sPq.empty()){
        int node = sPq.top()[1];
        int w = sPq.top()[0];
        int pare = sPq.top()[2];
        int dpt = sPq.top()[3];
        sPq.pop();
        if (active[node])continue;
        active[node] = true;
        binPar[node][0] = pare;
        binWeight[node][0] = w;
        depth[node] = dpt;
        for (auto p : adj[node]){
            if (!active[p.first])sPq.push({weight[node], p.first, node, dpt+1});
        }
    }

    initBin();    


    vector<int> ans;

    int q; cin >> q;
    while (q--){
        int s, t; cin >> s >> t;
        s--; t--;
        int LC = lca(s, t);
        //cout << s << " " << t << " " << LC << endl;
        //cout << getMin(s, depth[s]-depth[LC]) << " " << getMin(t, depth[t]-depth[LC]) << endl;
        ans.push_back(min(getMin(s, depth[s]-depth[LC]), getMin(t, depth[t]-depth[LC])));
    }

    for (int x : ans){
        cout << x << endl;
    }

    /*for (int i = 0; i < n; i++)cout << i << ": " << depth[i] << ",  ";
    cout << endl;

    for (int i = 0; i < n; i++){
        cout << i << ": " << endl << binPar[i][0] << " " << binPar[i][1] << " " << binPar[i][2] << endl;
        cout << binWeight[i][0] << " " << binWeight[i][1] << " " << binWeight[i][2] << endl;
    }*/



    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:131:21: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
  131 |     binPar[best][0] = best;
      |     ~~~~~~~~~~~~~~~~^~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46