Submission #501182

#	Time	Username	Problem	Language	Result	Execution time	Memory
501182		lukameladze	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1067 ms	67560 KiB

plan

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int N = 5e5 + 5,M = 300005;
int n,m,a[N],b[N],dist[M],p[M],c[N],x,y,ans[M],vert;
int fr[M],to[M],qq,l[M],sz[M],r[M];
vector <int> v1[N];
vector <pii> vv;
priority_queue < pii > q;
vector <pii> v[M];
void init() {
    for (int i = 1; i <= n; i++) {
        dist[i] = 1e9;
    }
}
int get_col(int a) {
    if (a == p[a]) return a;
    else return p[a] = get_col(p[a]);
}
void col(int a, int b) {
    a = get_col(a);
    b = get_col(b);
    if (a == b) return ;
    if (sz[a] < sz[b]) swap(a,b);
    sz[a] += sz[b];
    sz[b] = 0;
    p[b] = a;
}
void binsearch() {
    for (int i = 0; i < m; i++) {
        v1[i].clear();
    }
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        sz[i] = 1;
    }
    int q = qq;
    for (int i = 1; i <= q; i++) {
        v1[(l[i] + r[i])/2].pb(i);
    }
    for (int j = 0; j < m; j++) {
        col(a[vv[j].s],b[vv[j].s]);
        for (int j1 = 0; j1 < v1[j].size(); j1++) {
            int id = v1[j][j1];
            if (get_col(fr[id]) == get_col(to[id])) {
                ans[id] = vv[j].f;
                r[id] = j - 1;
            } else l[id] = j + 1;
        }
    }
}
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    init();
    for (int i = 1; i <= m; i++) {
        cin>>a[i]>>b[i]>>c[i];
        v[a[i]].pb({b[i],c[i]});
        v[b[i]].pb({a[i],c[i]});
    }
    cin>>x;
    for (int i = 1; i <= x; i++) {
        cin>>vert;
        q.push({0,vert});
        dist[vert] = 0;
    }
    while (!q.empty()) {
        x = -(q.top().f);
        y = q.top().s;
        q.pop();
        if (dist[y] < x) continue;
        for (int j = 0; j < v[y].size(); j++) {
            int to = v[y][j].f; int cost = v[y][j].s;
            if (dist[to] > x + cost) {
                dist[to] = x + cost;
                q.push({-dist[to],to});
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        vv.pb({min(dist[a[i]],dist[b[i]]),i});
    }
    sort(vv.begin(),vv.end());
    reverse(vv.begin(),vv.end());
    cin>>qq;
    for (int i = 1; i <= qq; i++) {
        cin>>fr[i]>>to[i];
        l[i] = 0;
        r[i] = m - 1;
    }
    for (int i = 1; i <= 19; i++)
    binsearch();
    for (int i = 1; i <= qq; i++ ){
        cout<<ans[i]<<" ";
    }
}

Compilation message (stderr)

plan.cpp: In function 'void binsearch()':
plan.cpp:46:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int j1 = 0; j1 < v1[j].size(); j1++) {
      |                          ~~~^~~~~~~~~~~~~~
plan.cpp: At global scope:
plan.cpp:55:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   55 | main() {
      | ^~~~
plan.cpp: In function 'int main()':
plan.cpp:75:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int j = 0; j < v[y].size(); j++) {
      |                         ~~^~~~~~~~~~~~~

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