Submission #1297557

#TimeUsernameProblemLanguageResultExecution timeMemory
1297557hiepsimauhongEvacuation plan (IZhO18_plan)C++20
100 / 100
1249 ms56148 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long

#define FOR(I, L, R) for(int I(L) ; I <= (int)R ; ++I)
#define FOD(I, R, L) for(int I(R) ; I >= (int)L ; --I)
#define FOA(I, A) for(auto &I : A)

#define print(A,L,R) FOR(OK, L, R){if(abs(A[OK]) >= oo / 10)cout<<"- ";else cout<<A[OK]<<' ';}cout<<'\n';
#define prints(A) FOA(OK, A){cout<<OK<<' ';}cout << '\n';
#define printz(A,L,R) FOR(OK, 0, L){FOR(KO, 0, R){if(abs(A[OK][KO]) <= oo / 10)cout<<A[OK][KO]<<' ';else cout << "- ";} cout << '\n';}cout << '\n';

#define fs first
#define sd second
#define ii pair<int,int>
#define iii pair<int, ii>
#define all(A) A.begin(), A.end()
#define quickly ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FILE "BUFF"

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int oo = 1e18;

int n, m, q, k;
ii a[N], it[N];
vector<ii> g[N];

int dist[N];
priority_queue<ii, vector<ii>, greater<ii>> pq;

int L[N], R[N], ans[N];
bool check[N];
vector<int> query[N];

struct DSU{
        int parent[N];

        void reset(){
                FOR(i, 1, n){
                        parent[i] = 0;
                }
        }

        int found(int u){
                return (parent[u] == 0 ? u : (parent[u] = found(parent[u])));
        }

        void setting(int u, int v){
                int U = found(u);
                int V = found(v);

                if(U != V){
                        parent[V] = U;
                }
        }
} dsu;

void init(){
        cin >> n >> m;

        FOR(i, 1, n) dist[i] = oo;

        FOR(i, 1, m){
                int u, v, w;
                cin >> u >> v >> w;

                g[u].push_back({v, w});
                g[v].push_back({u, w});
        }

        cin >> k;

        FOR(i, 1, k){
                int u; cin >> u;
                pq.push({0, u});
                dist[u] = 0;
        }

        cin >> q;

        FOR(i, 1, q){
                int u, v;
                cin >> u >> v;
                it[i] = {u, v};
        }
}

void Dijkstra(){
        while(!pq.empty()){
                int u = pq.top().sd;
                int cost = pq.top().fs;
                pq.pop();

                if(cost > dist[u]){
                        continue;
                }

                FOA(e, g[u]){
                        int v = e.fs, w = e.sd;

                        if(dist[v] > dist[u] + w){
                                dist[v] = dist[u] + w;
                                pq.push({dist[v], v});
                        }
                }
        }
}

void PreWork(){
        Dijkstra();

        FOR(i, 1, n){
                a[i] = {dist[i], i};
        }

        sort(a + 1, a + 1 + n, greater<ii>());
}

void Working(){
        dsu.reset();
        FOR(i, 1, n) check[i] = 0;

        FOR(mid, 1, n){
                int u = a[mid].sd;
                check[u] = 1;

                FOA(e, g[u]){
                        int v = e.fs;
                        if(check[v]){
                                dsu.setting(u, v);
                        }
                }

                FOA(i, query[mid]){
                        int x = it[i].fs, y = it[i].sd;

                        if(dsu.found(x) == dsu.found(y)){
                                R[i] = mid - 1;
                                ans[i] = mid;
                        }
                        else{
                                L[i] = mid + 1;
                        }
                }

                query[mid].clear();
        }
}

void ParaBinary(){
        FOR(i, 1, q){
                L[i] = 1, R[i] = n;
                ans[i] = -1;
        }

        FOR(times, 1, 20){
                FOR(i, 1, q){
                        if(L[i] <= R[i]){
                                query[L[i] + R[i] >> 1].push_back(i);
                        }
                }
                Working();
        }

        FOR(i, 1, q){
                cout << a[ans[i]].fs << '\n';
        }
}

signed main(){ quickly
        if(fopen(FILE".inp", "r")){
                freopen(FILE".inp", "r", stdin);
                freopen(FILE".out", "w", stdout);
        }

        init();
        PreWork();
        ParaBinary();
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:175:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |                 freopen(FILE".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:176:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |                 freopen(FILE".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...