제출 #173427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
173427		tourist	Evacuation plan (IZhO18_plan)	C++14	100 / 100	914 ms	48080 KiB

plan

#include <bits/stdc++.h>

using namespace std;

#define pii pair < int, int >
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define ok puts("ok");

const int N = (int)2e5 + 7;
const int inf = (int)1e9 + 7;

vector < pii > gr[N];
vector < int > newgr[N];
int dist[N];
int p[N], pr[N], par[N];
set < pii > s;
bool was[N];
int up[22][N];
int tin[N], tout[N];
int tiktak;

void fun () {
    while (!s.empty()) {
        pii v = *s.begin();
        s.erase(s.begin());
        for (auto to : gr[v.sc]) {
            if (dist[to.fr] > dist[v.sc] + to.sc) {
                s.erase(mk(dist[to.fr], to.fr));
                dist[to.fr] = dist[v.sc] + to.sc;
                s.insert(mk(dist[to.fr], to.fr));
            }
        }
    }
}

int get_par (int v) {
    if (pr[v] == v) return v;
    return pr[v] = get_par(pr[v]);
}

void connect (int a, int b) {
    a = get_par(a);
    b = get_par(b);
    if (a != b) {
        pr[a] = b;
    }
}

bool upper (int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

void dfs (int v) {
    tin[v] = ++tiktak;
    up[0][v] = par[v];
    for (int i = 1; i <= 20; i++) {
        up[i][v] = up[i - 1][up[i - 1][v]];
    }
    for (int to : newgr[v]) {
        if (to != par[v]) {
            dfs(to);
        }
    }
    tout[v] = ++tiktak;
}

int get (int a, int b) {
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;
    for (int i = 20; i >= 0; i--) {
        if (!upper(up[i][a], b)) a = up[i][a];
    }
    return up[0][a];
}

main () {
    int n, m; scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        pr[i] = i;
        dist[i] = inf;
    }
    for (int i = 1; i <= m; i++) {
        int a, b, c; scanf ("%d %d %d", &a, &b, &c);
        gr[a].pb(mk(b, c));
        gr[b].pb(mk(a, c));
    }
    int k; scanf ("%d", &k);
    for (int i = 1; i <= k; i++) {
        int a; scanf ("%d", &a);
        dist[a] = 0;
        s.insert(mk(0, a));
    }
    fun();
    vector < pii > vec;
    for (int i = 1; i <= n; i++) {
        vec.pb(mk(dist[i], i));
    }
    sort(vec.begin(), vec.end(), greater < pii > ());
    for (int i = 0; i < n; i++) {
        int a = vec[i].sc;
        was[a] = 1;
        for (auto to : gr[a]) {
            int b = to.fr;
            if (was[b]) {
                b = get_par(b);
                if (a != b) {
            	    connect(b, a);
        	        par[b] = a;
	                newgr[b].pb(a);
                	newgr[a].pb(b);
                }
            }
        }
    }
    par[vec[n - 1].sc] = vec[n - 1].sc;
    dfs(vec[n - 1].sc);
    int q; scanf ("%d", &q);
    while (q--) {
        int a, b; scanf ("%d %d", &a, &b);
        int qwe = get(a, b);
        printf ("%d\n", dist[qwe]);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

plan.cpp:79:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
plan.cpp: In function 'int main()':
plan.cpp:80:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n, m; scanf("%d %d", &n, &m);
               ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:86:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b, c; scanf ("%d %d %d", &a, &b, &c);
                      ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:90:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int k; scanf ("%d", &k);
            ~~~~~~^~~~~~~~~~
plan.cpp:92:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a; scanf ("%d", &a);
                ~~~~~~^~~~~~~~~~
plan.cpp:120:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int q; scanf ("%d", &q);
            ~~~~~~^~~~~~~~~~
plan.cpp:122:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf ("%d %d", &a, &b);
                   ~~~~~~^~~~~~~~~~~~~~~~~

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