Submission #759183

#	Time	Username	Problem	Language	Result	Execution time	Memory
759183		Dan4Life	Game (IOI14_game)	C++17	15 / 100	1 ms	372 KiB

game

#include <iostream>
using namespace std;

int n, p[1501], sz[1501];
bool chk[1501][1501];
int findSet(int i){return i==p[i]?i:p[i]=findSet(p[i]);}
void unionSet(int i, int j){
    int x = findSet(i), y = findSet(j);
    if(x==y) return;
    if(sz[x]<sz[y]) swap(x,y);
    p[y] = x; sz[x]+=sz[y]; 
}

void initialize(int N){
    n = N; for(int i =0; i < N; i++) p[i]=i,sz[i]=1;
}

int hasEdge(int u, int v){
    int cnt = 0;
    if(findSet(u)==findSet(v)){
        chk[u][v]=chk[v][u]=1;
        return 0;
    }
    for(int i = 0; i < n and cnt<2; i++)
        if(findSet(i)==u)
            for(int j = 0; j < n and cnt<2; j++)
                if(findSet(j)==v and !chk[i][j]) cnt++;
    if(cnt==1) unionSet(u,v); 
    chk[u][v]=chk[v][u]=1;
    return cnt==1;
}

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