Submission #502159

#	Time	Username	Problem	Language	Result	Execution time	Memory
502159		LucaIlie	Evacuation plan (IZhO18_plan)	C++17	41 / 100	669 ms	22268 KiB

plan

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

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];
    vector <int> comp[MAX_N];
    vector <int> aux;

    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 ) {
        int i, j;

        x = findSef( x );
        y = findSef( y );

        if ( x == y )
            return;
        i = j = 0;
        while ( i < comp[x].size() && j < comp[y].size() ) {
            if ( comp[x][i] < comp[y][j] ) {
                aux.push_back( comp[x][i] );
                i++;
            } else {
                aux.push_back( comp[y][j] );
                j++;
            }
            if ( aux.size() >= 2 && aux[aux.size() - 1] == aux[aux.size() - 2] ) {
                ans[aux[aux.size() - 1]] = danger;
                aux.pop_back();
                aux.pop_back();
            }
        }
        while ( i < comp[x].size() ) {
            aux.push_back( comp[x][i] );
            i++;
            if ( aux.size() >= 2 && aux[aux.size() - 1] == aux[aux.size() - 2] ) {
                ans[aux[aux.size() - 1]] = danger;
                aux.pop_back();
                aux.pop_back();
            }
        }
        while ( j < comp[y].size() ) {
            aux.push_back( comp[y][j] );
            j++;
            if ( aux.size() >= 2 && aux[aux.size() - 1] == aux[aux.size() - 2] ) {
                ans[aux[aux.size() - 1]] = danger;
                aux.pop_back();
                aux.pop_back();
            }
        }

        sef[y] = x;
        comp[x].clear();
        comp[y].clear();
        comp[x] = aux;
        aux.clear();
    }
};

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].push_back( i );
        ds.comp[y].push_back( 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 );

    if ( q >= 90000 )
        return 1;
    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;
}
/**
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

Compilation message (stderr)

plan.cpp: In member function 'void dsu::join(int, int, int)':
plan.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         while ( i < comp[x].size() && j < comp[y].size() ) {
      |                 ~~^~~~~~~~~~~~~~~~
plan.cpp:53:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         while ( i < comp[x].size() && j < comp[y].size() ) {
      |                                       ~~^~~~~~~~~~~~~~~~
plan.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         while ( i < comp[x].size() ) {
      |                 ~~^~~~~~~~~~~~~~~~
plan.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         while ( j < comp[y].size() ) {
      |                 ~~^~~~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:150:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<muchie>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |             for ( i = 0; i < muchii[x].size(); i++ ) {
      |                          ~~^~~~~~~~~~~~~~~~~~
plan.cpp:170:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<muchie>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |         for ( j = 0; j < muchii[x].size(); j++ ) {
      |                      ~~^~~~~~~~~~~~~~~~~~

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