제출 #1148336

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148336		dosts	게임 (IOI14_game)	C++20	42 / 100	1095 ms	5960 KiB

game

//DOST SEFEROĞLU
#include <bits/stdc++.h>
#include "game.h"
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>


int noedge[1501][1501];
vi people[1501];
int dad[1501];

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

void unite(int x,int y) {
    for (auto it : people[x]) people[y].push_back(it);
    people[x].clear();
    dad[x] = y;
}

void initialize(int32_t n) {
    for (int i=1;i<=n;i++) for (int j = 1;j<=n;j++) noedge[i][j] = 0;
    for (int i = 1;i<=n;i++) {
        people[i].clear();
        dad[i] = i;
        people[i].push_back(i);
    }
}

int32_t hasEdge(int32_t u, int32_t v) {
    u++,v++;
    int a = find(u),b = find(v);
    if (a == b) {
        noedge[u][v] = noedge[v][u] = 1;
        return 0;
    }
    int bos = 0;
    for (auto it : people[a]) {
        for (auto it2 : people[b]) {
            if (noedge[it][it2]) continue;
            bos++;
        }
    }
    if (bos == 1) {
        unite(a,b);
        return 1;
    }
    noedge[u][v] = noedge[v][u] = 1;
    return 0;
}

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