제출 #1131412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131412		tredsused70	Evacuation plan (IZhO18_plan)	C++20	100 / 100	972 ms	42024 KiB

plan

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
//#pragma GCC optimize("trapv")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define mpr make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int nmax = 100011, mod = 1000000007, inf = 2000010000, key = 200003, lg = 20, block = 300;
const ll infll = 4000000000000000000;
const ld eps = 1e-9;

int dist[nmax], color[nmax], used[nmax] = {0};
vector<array<int, 2>> graf[nmax];
vector<int> nodes[nmax], query[nmax];

void dickstra(int n) {
    set<array<int, 2>> st;
    for(int i = 1; i <= n; i++) {
        if(dist[i] == 0)
            st.insert({0, i});
    }
    while(!st.empty()) {
        auto cur = *st.begin();
        st.erase(st.begin());
        for(auto i : graf[cur[1]]) {
            if(dist[i[0]] > cur[0] + i[1]) {
                st.erase({dist[i[0]], i[0]});
                dist[i[0]] = cur[0] + i[1];
                st.insert({dist[i[0]], i[0]});
            }
        }
    }
    return ;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    fill(dist, dist + n + 1, inf);
    int u, v, w;
    for(int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        graf[u].pb({v, w});
        graf[v].pb({u, w});
    }
    int k;
    //cout << "Need k\n";
    cin >> k;
    for(int i = 0; i < k; i++) {
        cin >> u;
        dist[u] = 0;
    }
    dickstra(n);
    vector<array<int, 2>> order(n);
    for(int i = 0; i < n; i++) {
        order[i] = {dist[i + 1], i + 1};
        //cout << i + 1 << " " << dist[i + 1] << " v dist[v]\n";
    }

    sort(all(order));
    reverse(all(order));
    int q;
    //cout << "Need q\n";
    cin >> q;
    map<array<int, 2>, int> ans;
    vector<array<int, 2>> queries(q);
    for(int i = 0; i < q; i++) {
        cin >> u >> v;
        queries[i] = {u, v};
        query[u].pb(v);
        query[v].pb(u);
    }
    //cout << "Done\n";
    for(int i = 1; i <= n; i++) {
        color[i] = i;
        nodes[i].pb(i);
    }
    int colorv, colorj;
    for(int i = 0; i < n; i++) {
        v = order[i][1];
        used[v] = 1;
        //cout << "\n\nCURRENT NODE IS " << v << "\n";
        for(auto j : graf[v]) {
            if(!used[j[0]] || color[v] == color[j[0]])
                continue;
            //cout << "current edge: " << v << " " << j[0] << "\n";
            colorv = color[v];
            colorj = color[j[0]];
            if(nodes[colorv].size() < nodes[colorj].size())
                swap(colorv, colorj);
            //cout << "combine " << colorv << " with " << colorj << "\n";
            for(int u : nodes[colorj]) {
                //cout << "looking at " << u << "\n";
                for(int k : query[u]) {
                    if(colorv == color[k]) {
                        //cout << "FOUND ANSWER TO " << u << " " << k << "\n";
                        ans[{u, k}] = order[i][0];
                        ans[{k, u}] = order[i][0];
                    }
                }
            }
            for(int u : nodes[colorj]) {
                //cout << u << " is now color " << colorv << "\n";
                nodes[colorv].pb(u);
                color[u] = colorv;
            }
        }
    }
    for(int i = 0; i < q; i++)
        cout << ans[{queries[i][0], queries[i][1]}] << "\n";
    return ;
}

int main()
{
    //freopen("wormsort.in","r",stdin);
    //freopen("wormsort.out","w",stdout);
    //ios_base::sync_with_stdio(0);cin.tie(0);
    srand(8713);
    //init();
    int t = 1;
    //cin >> t;
    //int t_ = t;
    //t = rdi();
    while(t--) {
        //cout << "Case #" << t_ - t << ": ";
        solve();
    }
    //flush();
    return 0;
}

/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

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