Submission #501152

#	Time	Username	Problem	Language	Result	Execution time	Memory
501152		lukameladze	Evacuation plan (IZhO18_plan)	C++14	22 / 100	4049 ms	524292 KiB

plan

# include <bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int N = 5e5 + 5, B = 700;
int n,m,a[N],b[N],dist[N],p[N],c[N],x,vert[N],y,ds,bl,ans,all;
vector <pii > vv;
priority_queue < pii > q;
vector <pii> v[N];
int startt[N],endd[N];
vector <int> par[1000],curvec;
void init() {
    for (int i = 1; i <= n; i++) {
        dist[i] = 1e10;
    }
}
int get_coll(int a) {
    if (a == curvec[a]) return a;
    else return curvec[a] = get_coll(curvec[a]);
}
void coll(int a, int b) {
    a = get_coll(a);
    b = get_coll(b);
    if (a == b) return ;
    curvec[b] = a;
    //if (par[a] == par[b])
}
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 ;
    p[b] = a;
}
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[i];
        q.push({0,vert[i]});
        dist[vert[i]] = 0;
    }
    while (!q.empty()) {
        x = -(q.top().f);
        y = q.top().s;
        q.pop();
        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 = 0; i <= n; i++) {
        p[i] = i;
        startt[i] = -1;
    }
    for (int i = 1; i <= m; i++) {
        ds = min(dist[a[i]],dist[b[i]]);
        vv.pb({ds,i});
    }
    sort(vv.begin(),vv.end());
    reverse(vv.begin(),vv.end());
    for (int i = 0; i < vv.size(); i++) {
        bl = i/B;
        if (startt[bl] == -1) {
            startt[bl] = i; 
        } 
        endd[bl] = i;
    }
    bl = (m - 1)/B;
    par[bl] = vector <int> (n+1,0);
    for (int j = 1; j <= n; j++) {
        par[bl][j] = get_col(j);
    }
    all = (m - 1) / B;
    for (int i = 0; i < vv.size(); i++) {
        col(a[vv[i].s],b[vv[i].s]);
        bl = i/B;
        if (i == endd[bl]) {
            par[bl] = vector <int> (n+1,0);
            for (int j = 1; j <= n; j++) {
                par[bl][j] = get_col(j);
            }
        }
    }
    vector <int> v1 = vector <int> (n + 1, 0);
    for (int i = 1; i <= n; i++) {
        v1[i] = i;
    }
    int q;
    cin>>q;
    while(q--) {
        cin>>x>>y;
        for (int j = 0; j <= all; j++) {
            if (par[j][x] == par[j][y]) {
                //cout<<j<<endl;
                if (j == 0) {
                    curvec = v1;
                } else curvec = par[j - 1];
               // cout<<startt[j]<<" "<<endd[j]<<endl;
                for (int j1 = startt[j]; j1 <= endd[j]; j1++) {
                    coll(a[vv[j1].s],b[vv[j1].s]);
                    if (get_coll(x) == get_coll(y)) {
                        ans = vv[j1].f;
                        break;
                    }
                }
                cout<<ans<<"\n";break;
            }
        }
    }
    
}

Compilation message (stderr)

plan.cpp:41:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 | main() {
      | ^~~~
plan.cpp: In function 'int main()':
plan.cpp:60:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int j = 0; j < v[y].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
plan.cpp:78:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 0; i < vv.size(); i++) {
      |                     ~~^~~~~~~~~~~
plan.cpp:91:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i = 0; i < vv.size(); i++) {
      |                     ~~^~~~~~~~~~~

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