Submission #342849

#	Time	Username	Problem	Language	Result	Execution time	Memory
342849		Rakhmand	Evacuation plan (IZhO18_plan)	C++14	35 / 100	4051 ms	166868 KiB

plan

//
//  main.cpp
//  torelax
//
//  Created by Rakhman on 11/15/20.
//

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>

#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define no_answer {cout << "NO"; exit(0);}
#define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k)

const long long mxn = 2e6 + 110;
const long long mnn = 1e1 + 1;
const long long mod = 1e9 + 7;
const long long inf = 1e18;
const long long OO = 1e9;

typedef long long llong;
typedef unsigned long long ullong;

using namespace std;

int n, m, k, d[mxn], p[mxn], sz[mxn], ans[mxn];
vector<pair<int, int> > g[mxn];
set<pair<int, int> > st;
bool used[mxn];
set<int> s[mxn];

int get_p(int x){
    if(x == p[x]) return x;
    else return get_p(p[x]);
}

void get(int u, int v){
    int U = get_p(u), V = get_p(v);
    if(U == V) return ;
    if(s[U].size() > s[V].size()){
        swap(U, V);
    }
    p[U] = V;
    while(s[U].size() != 0){
        int x = *(s[U].begin());
        s[U].erase(s[U].begin());
        int cnt = s[V].erase(x);
        if(cnt > 0){
            ans[x] = d[v];
        }else{
            s[V].insert(x);
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        d[i] = OO;
        p[i] = i;
        sz[i] = 1;
    }
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    cin >> k;
    for(int i = 1; i <= k; i++){
        int x;
        cin >> x;
        d[x] = 0;
        st.insert({0, x});
    }
    while(st.size() != 0){
        int x = (st.begin() -> second);
        st.erase(st.begin());
        for(int i = 0; i < g[x].size(); i++){
            int to = g[x][i].F, w = g[x][i].S;
            if(d[to] > d[x] + w){
                st.erase({d[to], to});
                d[to] = d[x] + w;
                st.insert({d[to], to});
            }
        }
    }
    int q;
    cin >> q;
    for(int i = 1; i <= q; i++){
        int u, v;
        cin >> u >> v;
        s[u].insert(i);
        s[v].insert(i);
    }
    vector<pair<int, int> > v;
    for(int i = 1; i <= n; i++){
        v.push_back({d[i], i});
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    for(int i = 0; i < v.size(); i++){
        if(i == 0) continue;
        int x = v[i].second;
        for(int j = 0; j < g[x].size(); j++){
            int to = g[x][j].first;
            if(d[to] >= d[x]){
                get(to, x);
            }
        }
    }
    for(int i = 1; i <= q; i++){
        cout << ans[i] << nl;
    }
}


/*
 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
 
 */

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:106:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int i = 0; i < g[x].size(); i++){
      |                        ~~^~~~~~~~~~~~~
plan.cpp:129:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
plan.cpp:132:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         for(int j = 0; j < g[x].size(); j++){
      |                        ~~^~~~~~~~~~~~~

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