Submission #847579

#	Time	Username	Problem	Language	Result	Execution time	Memory
847579		12345678	Game (IOI14_game)	C++17	100 / 100	274 ms	28972 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1505;
int N, dsu[nx], c[nx][nx];
vector<vector<int>> d(nx);
bool q[nx][nx];

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

void initialize(int n) {
    for (int i=0; i<n; i++) dsu[i]=i, d[i].push_back(i);
    N=n;
}

int hasEdge(int u, int v) {
    q[u][v]=q[v][u]=1;
    int pu=find(u), pv=find(v);
    if (pu==pv) return 0;
    c[pu][pv]++; c[pv][pu]++;
    if (c[pu][pv]==d[pu].size()*d[pv].size())
    {
        dsu[pu]=pv;
        for (auto x:d[pu]) d[pv].push_back(x);
        for (int i=0; i<N; i++) c[pv][i]=c[i][pv]=c[pv][i]+c[pu][i];
        return 1;
    } 
    else return 0;
}

Compilation message (stderr)

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if (c[pu][pv]==d[pu].size()*d[pv].size())
      |         ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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