Submission #847575

#	Time	Username	Problem	Language	Result	Execution time	Memory
847575		12345678	게임 (IOI14_game)	C++17	42 / 100	1031 ms	6240 KiB

game

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

using namespace std;

const int nx=1505;
int N, dsu[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;
    int cnt=0;
    for (auto x:d[pu]) for (auto y:d[pv]) if (q[x][y]) cnt++;
    if (cnt==d[pu].size()*d[pv].size())
    {
        dsu[pu]=pv;
        for (auto x:d[pu]) d[pv].push_back(x);
        return 1;
    } 
    else return 0;
}

Compilation message (stderr)

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

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