Submission #342740

#	Time	Username	Problem	Language	Result	Execution time	Memory
342740		Rakhmand	Evacuation plan (IZhO18_plan)	C++14	41 / 100	4066 ms	73728 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];
vector<pair<int, int> > g[mxn];
set<pair<int, int> > st;
bool used[mxn];

void dfs(int x, int w){
    used[x] = true;
    for(int i = 0; i < g[x].size(); i++){
        int to = g[x][i].F;
        if(used[to] == 1) continue;
        else{
            if(d[to] >= w) dfs(to, w);
        }
    }
}

bool check(int x, int fin, int w){
    for(int i = 1; i <= n; i++) used[i] = false;
    dfs(x, w);
    return used[fin];
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        d[i] = OO;
    }
    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;
        int l = 0, r = min(d[u], d[v]);
        while(r - l > 1){
            int m = (r + l) / 2;
            if(check(u, v, m)){
                l = m;
            }else{
                r = m;
            }
        }
        if(check(u, v, r)) cout << r << nl;
        else cout << l << 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 'void dfs(int, int)':
plan.cpp:60: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]
   60 |     for(int i = 0; i < g[x].size(); i++){
      |                    ~~^~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:96: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]
   96 |         for(int i = 0; i < g[x].size(); i++){
      |                        ~~^~~~~~~~~~~~~

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