Submission #892756

#	Time	Username	Problem	Language	Result	Execution time	Memory
892756		raul2008487	Game (IOI14_game)	C++17	100 / 100	306 ms	34828 KiB

game

#include<bits/stdc++.h>
#define ll long long
#define vl vector<ll>
#include "game.h"
using namespace std;
const int sz = 1505;
ll a[sz][sz];
struct DSU{
    vl e, ne;
    void init(ll n){
        e.assign(n+1, -1);
        ne.assign(n+1, 0);
    }
    ll base(ll x){
        if(e[x] < 0){
            return x;
        }
        return e[x] = base(e[x]);
    }
    bool unite(ll x, ll y){
        x = base(x);
        y = base(y);
        bool as = 0;
        if(x == y){assert(0);}
        if(e[x] > e[y]){
            swap(x, y);
        }
        a[x][y]++;
        a[y][x]++;
        ll nume = ne[x] + ne[y] + a[x][y];
        ll cd = e[x] + e[y];
        ll fe = (cd * (cd + 1) / 2);
        if(nume == fe){
            e[x] += e[y];
            e[y] = x;
            ne[x] = fe;
            for(int i = 0; i<e.size()-1; i++){
                if(a[i][y]){
                    a[i][x] += a[i][y];
                    a[x][i] += a[i][y];
                }
            }
            return true;
        }
        else{
            return 0;
        }

    }
};
DSU dsu;
void initialize(int n) {
    dsu.init(n);
    ll i, j;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            a[i][j] = 0;
        }
    }
}
int hasEdge(int u, int v) {
    if(dsu.unite(u, v)){
        return 1;
    }
    return 0;
}
/*
5
0 2
0 4
1 3
3 4
0 3
0 1
4 1
1 2
4 2

*/

Compilation message (stderr)

game.cpp: In member function 'bool DSU::unite(long long int, long long int)':
game.cpp:37:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for(int i = 0; i<e.size()-1; i++){
      |                            ~^~~~~~~~~~~
game.cpp:23:14: warning: unused variable 'as' [-Wunused-variable]
   23 |         bool as = 0;
      |              ^~

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 58 / 58