Submission #1054424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054424		vjudge1	Evacuation plan (IZhO18_plan)	C++17	100 / 100	344 ms	57196 KiB

plan

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

#define ll long long
#define ld long double
#define FOR(i, a, b) for(int i=(a), _b=(b); i<=b; i++)
#define FORD(i, a, b) for(int i=(a), _b=(b); i>=b; i--)
#define BIT(i, j) ((i>>j)&1)
#define pb push_back
#define ii pair<ll, ll>
#define pii pair<ll, ii>
#define fi first
#define se second

const ll inf = 1e18;
const ll N = 1e5+5;
ll n, m, q, k, s[N], p[N], dist[N], ans[N], par[N], u, v, w;
vector<ii> adj[N];
set<ll> S[N];
priority_queue<ii, vector<ii>, greater<ii>> pq;

void dijkstra(){
    fill(dist+1, dist+n+1, inf);
    FOR(i, 1, k){
        dist[s[i]] = 0;
        pq.push({0, s[i]});
    }

    while(!pq.empty()){
        ll val = pq.top().fi;
        ll u = pq.top().se;
        pq.pop();
        if(val!=dist[u]) continue;
        for(auto e:adj[u]){
            if(dist[e.fi] > dist[u] + e.se){
                dist[e.fi] = dist[u] + e.se;
                pq.push({dist[e.fi], e.fi});
            }
        }
    }
}

ll find_set(ll u){
    if(par[u]==u) return u;
    return par[u] = find_set(par[u]);
}
void union_set(ll u, ll v, ll w){
    u = find_set(u);
    v = find_set(v);
    if(u == v) return;
    if(u > v) swap(u, v);
    for(ll x: S[v]){
        if(S[u].find(x) != S[u].end()){
            ans[x] = w;
            S[u].erase(x);
        }
        else S[u].insert(x);
    }
    S[v].clear();
    par[v] = u;
}
void inp(){
    cin >> n >> m;
    FOR(i, 1, m){
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    cin >> k;
    FOR(i, 1, k) cin >> s[i];
    cin >> q;
    FOR(i, 1, q){
        ll x, y;
        cin >> x >> y;
        S[x].insert(i);
        S[y].insert(i);
    }
}

void solve(){
    dijkstra();
    FOR(i, 1, n) p[i] = i;
    sort(p+1, p+n+1, [](ll x, ll y){
        return dist[x] > dist[y];
    });

    FOR(i, 1, n) par[i] = i;
    FOR(i, 1, n){
        ll u = p[i];
        for(auto e: adj[u]){
            if(dist[e.fi] >= dist[u]){
                union_set(u, e.fi, dist[u]);
            }
        }
    }

    FOR(i, 1, q) cout << ans[i] << '\n';
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    inp();
    solve();
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void dijkstra()':
plan.cpp:6:37: warning: unused variable '_b' [-Wunused-variable]
    6 | #define FOR(i, a, b) for(int i=(a), _b=(b); i<=b; i++)
      |                                     ^~
plan.cpp:24:5: note: in expansion of macro 'FOR'
   24 |     FOR(i, 1, k){
      |     ^~~
plan.cpp: In function 'void inp()':
plan.cpp:6:37: warning: unused variable '_b' [-Wunused-variable]
    6 | #define FOR(i, a, b) for(int i=(a), _b=(b); i<=b; i++)
      |                                     ^~
plan.cpp:64:5: note: in expansion of macro 'FOR'
   64 |     FOR(i, 1, m){
      |     ^~~
plan.cpp:6:37: warning: unused variable '_b' [-Wunused-variable]
    6 | #define FOR(i, a, b) for(int i=(a), _b=(b); i<=b; i++)
      |                                     ^~
plan.cpp:70:5: note: in expansion of macro 'FOR'
   70 |     FOR(i, 1, k) cin >> s[i];
      |     ^~~
plan.cpp:6:37: warning: unused variable '_b' [-Wunused-variable]
    6 | #define FOR(i, a, b) for(int i=(a), _b=(b); i<=b; i++)
      |                                     ^~
plan.cpp:72:5: note: in expansion of macro 'FOR'
   72 |     FOR(i, 1, q){
      |     ^~~
plan.cpp: In function 'void solve()':
plan.cpp:6:37: warning: unused variable '_b' [-Wunused-variable]
    6 | #define FOR(i, a, b) for(int i=(a), _b=(b); i<=b; i++)
      |                                     ^~
plan.cpp:82:5: note: in expansion of macro 'FOR'
   82 |     FOR(i, 1, n) p[i] = i;
      |     ^~~
plan.cpp:6:37: warning: unused variable '_b' [-Wunused-variable]
    6 | #define FOR(i, a, b) for(int i=(a), _b=(b); i<=b; i++)
      |                                     ^~
plan.cpp:87:5: note: in expansion of macro 'FOR'
   87 |     FOR(i, 1, n) par[i] = i;
      |     ^~~
plan.cpp:6:37: warning: unused variable '_b' [-Wunused-variable]
    6 | #define FOR(i, a, b) for(int i=(a), _b=(b); i<=b; i++)
      |                                     ^~
plan.cpp:88:5: note: in expansion of macro 'FOR'
   88 |     FOR(i, 1, n){
      |     ^~~
plan.cpp:6:37: warning: unused variable '_b' [-Wunused-variable]
    6 | #define FOR(i, a, b) for(int i=(a), _b=(b); i<=b; i++)
      |                                     ^~
plan.cpp:97:5: note: in expansion of macro 'FOR'
   97 |     FOR(i, 1, q) cout << ans[i] << '\n';
      |     ^~~

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