Submission #383681

#	Time	Username	Problem	Language	Result	Execution time	Memory
383681		BartolM	Evacuation plan (IZhO18_plan)	C++17	100 / 100	906 ms	53052 KiB

plan

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=1e5+5;
const int LOG=18;

int n, m, k, q;
int dist[N], P[N], dep[N];
vector <pii> ls[N], ls_st[N];
set <pii> S;
vector <pip> v;
int par[LOG][N], val[LOG][N];

int name(int x) {
    if (x==P[x]) return x;
    P[x]=name(P[x]);
    return P[x];
}

int mrg(int a, int b) {
    a=name(a); b=name(b);
    if (a==b) return 0;
    P[a]=b;
    return 1;
}

void build() {
    for (int i=1; i<LOG; ++i) {
        for (int j=1; j<=n; ++j) {
            par[i][j]=par[i-1][par[i-1][j]];
            val[i][j]=min(val[i-1][j], val[i-1][par[i-1][j]]);
        }
    }
}

int lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x, y);
    for (int i=LOG-1; i>=0; --i) {
        if (dep[x]-(1<<i)>=dep[y]) x=par[i][x];
    }
    if (x==y) return x;
    for (int i=LOG-1; i>=0; --i) {
        if (par[i][x]!=par[i][y]) x=par[i][x], y=par[i][y];
    }
    return par[0][x];
}

int popni(int x, int d) {
    int ret=INF;
    for (int i=LOG-1; i>=0; --i) {
        if (dep[x]-(1<<i)>=d) {
            ret=min(ret, val[i][x]);
            x=par[i][x];
        }
    }
    return ret;
}

void dfs(int node, int rod) {
    dep[node]=dep[rod]+1;
    par[0][node]=rod;
    for (pii sus:ls_st[node]) {
        if (sus.X==rod) continue;
        dfs(sus.X, node);
        val[0][sus.X]=sus.Y;
    }
}

void dijkstra() {
    while (!S.empty()) {
        pii node=*S.begin();
        S.erase(S.begin());
        for (pii sus:ls[node.Y]) {
            if (dist[sus.X]<=sus.Y+node.X) continue;
            if (S.count(mp(dist[sus.X], sus.X))) S.erase(mp(dist[sus.X], sus.X));
            dist[sus.X]=sus.Y+node.X;
            S.insert(mp(dist[sus.X], sus.X));
        }
    }
}

void solve() {
    dijkstra();
    for (int i=1; i<=n; ++i) {
        P[i]=i;
        for (pii sus:ls[i]) {
            int ed=min(dist[i], dist[sus.X]);
            if (sus.X>i) v.pb(mp(ed, mp(i, sus.X)));
        }
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    for (int i=0; i<v.size(); ++i) {
        if (mrg(v[i].Y.X, v[i].Y.Y)) {
            ls_st[v[i].Y.X].pb(mp(v[i].Y.Y, v[i].X));
            ls_st[v[i].Y.Y].pb(mp(v[i].Y.X, v[i].X));
        }
    }
    dfs(1, 0);
    build();
    for (int i=0; i<q; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        int lc=lca(a, b);
        printf("%d\n", min(popni(a, dep[lc]), popni(b, dep[lc])));
    }
}

void load() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<m; ++i) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        ls[a].pb(mp(b, c));
        ls[b].pb(mp(a, c));
    }
    scanf("%d", &k);
    memset(dist, INF, sizeof dist);
    for (int i=0; i<k; ++i) {
        int x;
        scanf("%d", &x);
        S.insert(mp(0, x));
        dist[x]=0;
    }
    scanf("%d", &q);
}

int main() {
    load();
    solve();
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void solve()':
plan.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for (int i=0; i<v.size(); ++i) {
      |                   ~^~~~~~~~~
plan.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp: In function 'void load()':
plan.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  122 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  125 |         scanf("%d %d %d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:129:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  129 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
plan.cpp:133:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  133 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
plan.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  137 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~

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