제출 #1167078

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167078		SmuggingSpun	Evacuation plan (IZhO18_plan)	C++20	100 / 100	447 ms	23492 KiB

plan

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
const int lim = 1e5 + 5;
template<class T>bool minimize(T& a, T b){
    if(a > b){
        a = b;
        return true;
    }
    return false;
}
vector<pair<int, int>>g[lim], parent[lim];
int n, m, k, q, dsu_time = -1, d[lim], sz[lim];
int find_set(int N, int time){
    while(true){
        int par_N = parent[N][lower_bound(parent[N].begin(), parent[N].end(), make_pair(time, lim)) - parent[N].begin() - 1].second;
        if(N == par_N){
            break;
        }
        N = par_N;
    }
    return N;
}
void merge(int u, int v){
    if((u = find_set(u, dsu_time + 1)) != (v = find_set(v, dsu_time + 1))){
        if(sz[u] < sz[v]){
            swap(u, v);
        }
        parent[v].emplace_back(dsu_time + 1, u);
        sz[u] += sz[v];
    }
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    cin >> k;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
    memset(d, 0x3f, sizeof(d));
    for(int i = 0; i < k; i++){
        int u;
        cin >> u;
        pq.emplace(d[u] = 0, u);
    }
    while(!pq.empty()){
        auto [du, u] = pq.top();
        pq.pop();
        if(du == d[u]){
            for(auto& [v, w] : g[u]){
                if(minimize(d[v], du + w)){
                    pq.emplace(d[v], v);
                }
            }
        }
    }
    vector<int>p(n);
    iota(p.begin(), p.end(), 1);
    sort(p.begin(), p.end(), [&] (int i, int j){
        return d[i] > d[j];
    });
    memset(sz, 0, sizeof(sz));
    for(int& i : p){
        parent[i].emplace_back(-(sz[i] = 1), i);
        for(auto& [j, foo] : g[i]){
            if(!parent[j].empty()){
                merge(i, j);
            }
        }
        dsu_time++;
    }
    cin >> q;
    for(int _ = 0; _ < q; _++){
        int s, t, low = 0, high = n - 2, ans = n - 1;
        cin >> s >> t;
        while(low <= high){
            int mid = (low + high) >> 1;
            if(find_set(s, mid) != find_set(t, mid)){
                low = mid + 1;
            }
            else{
                high = (ans = mid) - 1;
            }
        }
        cout << d[p[ans]] << "\n";
    }
}

컴파일 시 표준 에러 (stderr) 메시지

plan.cpp: In function 'int main()':
plan.cpp:36:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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