Submission #502170

#	Time	Username	Problem	Language	Result	Execution time	Memory
502170		LucaIlie	Evacuation plan (IZhO18_plan)	C++17	100 / 100	835 ms	59200 KiB

plan

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>

using namespace std;

#define MAX_N 100000
#define MAX_Q 100000
#define MAX_DIST 500000000

struct muchie {
    int vec, dist;
};

struct aaa {
    int nod, dist;

    bool operator < (const aaa &aux) const {
        return dist > aux.dist;
    }
};

int ans[MAX_Q];

struct dsu {
    int sef[MAX_N];
    set <int> comp[MAX_N];

    void init( int n ) {
        int i;

        for ( i = 0; i < n; i++ )
            sef[i] = i;
    }

    int findSef( int x ) {
        if ( sef[x] != x )
            sef[x] = findSef( sef[x] );
        return sef[x];
    }

    void join( int x, int y, int danger ) {
        x = findSef( x );
        y = findSef( y );

        if ( x == y )
            return;

        if ( comp[x].size() < comp[y].size() )
            swap( x, y );

        for( auto k : comp[y] ) {
            if ( comp[x].count( k ) )
                ans[k] = danger;
            else
                comp[x].insert( k );
        }

        sef[y] = x;
    }
};

struct bbb {
    int dist, nod;

    bool operator < (const bbb &a) const {
        if ( dist == a.dist )
            return nod < a.nod;
        return dist < a.dist;
    }
};

int dist[MAX_N], viz[MAX_N];
vector <muchie> muchii[MAX_N];
priority_queue <aaa> pq;
dsu ds;
bbb v[MAX_N];

int main() {
    int n, m, k, q, x, y, d, i, j;
    aaa aux;

    cin >> n >> m;
    for ( i = 0; i < m; i++ ) {
        cin >> x >> y >> d;
        x--;
        y--;
        muchii[x].push_back( { y, d } );
        muchii[y].push_back( { x, d } );
    }

    for ( i = 0; i < n; i++ )
        dist[i] = MAX_DIST + 1;

    cin >> k;
    for ( i = 0; i < k; i++ ) {
        cin >> x;
        x--;
        dist[x] = 0;
        pq.push( { x, 0 } );
    }

    cin >> q;
    for ( i = 0; i < q; i++ ) {
        cin >> x >> y;
        x--;
        y--;
        ds.comp[x].insert( i );
        ds.comp[y].insert( i );
    }

    while ( !pq.empty() ) {
        aux = pq.top();
        pq.pop();
        x = aux.nod;

        if ( viz[x] == 0 ) {
            viz[x] = 1;
            for ( i = 0; i < muchii[x].size(); i++ ) {
                y = muchii[x][i].vec;
                d = muchii[x][i].dist;
                if ( dist[x] + d < dist[y] ) {
                    dist[y] = dist[x] + d;
                    pq.push( { y, dist[y] } );
                }
            }
        }
    }

    for ( i = 0; i < n; i++ )
        v[i] = { dist[i], i };
    sort( v, v + n );

    ds.init( n );
    for ( i = n - 1; i >= 0; i-- ) {
        x = v[i].nod;
        for ( j = 0; j < muchii[x].size(); j++ ) {
            y = muchii[x][j].vec;
            if ( bbb{ dist[x], x } < bbb{ dist[y], y } )
                ds.join( x, y, dist[x] );
        }
    }

    for ( i = 0; i < q; i++ )
        cout << ans[i] << "\n";

    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:121:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<muchie>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |             for ( i = 0; i < muchii[x].size(); i++ ) {
      |                          ~~^~~~~~~~~~~~~~~~~~
plan.cpp:139:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<muchie>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |         for ( j = 0; j < muchii[x].size(); j++ ) {
      |                      ~~^~~~~~~~~~~~~~~~~~

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