Submission #1079367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079367		hirayuu_oj	Game (IOI14_game)	C++17	0 / 100	1 ms	604 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
struct unionfind{
    int sz;
    vector<int> tree;
    unionfind(int size):sz(size),tree(size,-1){}
    int leader(int p){
        int pos;
        while(tree[p]>=0)p=tree[p];
        while(tree[pos]>=0){
            int bef=tree[pos];
            tree[pos]=p;
            pos=tree[pos];
        }
        return p;
    }
    int size(int p){
        return -tree[leader(p)];
    }
    bool merge(int x,int y){
        x=leader(x);
        y=leader(y);
        if(x==y)return false;
        if(tree[x]>tree[y])swap(x,y);
        tree[x]+=tree[y];
        tree[y]=x;
        return true;
    }
};
vector<vector<int>> edge;
unionfind uni(0);
int N;
void initialize(int n) {
    N=n;
    edge.resize(n,vector<int>(n,0));
    uni=unionfind(n);
}

int hasEdge(int u, int v) {
    u=uni.leader(u);
    v=uni.leader(v);
    assert(u!=v);
    edge[u][v]++;
    edge[v][u]++;
    if(uni.size(u)*uni.size(v)==edge[u][v]){
        uni.merge(u,v);
        if(uni.leader(u)!=u)swap(u,v);
        rep(i,N){
            if(i==u)continue;
            if(i==v)continue;
            edge[i][u]+=edge[i][v];
            edge[u][i]+=edge[v][i];
        }
        return 1;
    }
    return 0;
}

Compilation message (stderr)

game.cpp: In member function 'int unionfind::leader(int)':
game.cpp:13:17: warning: unused variable 'bef' [-Wunused-variable]
   13 |             int bef=tree[pos];
      |                 ^~~
game.cpp: In function 'int hasEdge(int, int)':
game.cpp:12:23: warning: 'pos' is used uninitialized in this function [-Wuninitialized]
   12 |         while(tree[pos]>=0){
      |                       ^
game.cpp:10:13: note: 'pos' was declared here
   10 |         int pos;
      |             ^~~
game.cpp:12:23: warning: 'pos' is used uninitialized in this function [-Wuninitialized]
   12 |         while(tree[pos]>=0){
      |                       ^
game.cpp:10:13: note: 'pos' was declared here
   10 |         int pos;
      |             ^~~
game.cpp:12:23: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   12 |         while(tree[pos]>=0){
      |                       ^
game.cpp:10:13: note: 'pos' was declared here
   10 |         int pos;
      |             ^~~
game.cpp:12:23: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   12 |         while(tree[pos]>=0){
      |                       ^
game.cpp:10:13: note: 'pos' was declared here
   10 |         int pos;
      |             ^~~
game.cpp:12:23: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   12 |         while(tree[pos]>=0){
      |                       ^
game.cpp:10:13: note: 'pos' was declared here
   10 |         int pos;
      |             ^~~
game.cpp:12:23: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   12 |         while(tree[pos]>=0){
      |                       ^
game.cpp:10:13: note: 'pos' was declared here
   10 |         int pos;
      |             ^~~
game.cpp:12:23: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   12 |         while(tree[pos]>=0){
      |                       ^
game.cpp:10:13: note: 'pos' was declared here
   10 |         int pos;
      |             ^~~

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