제출 #689413

#제출 시각아이디문제언어결과실행 시간메모리
689413sharaelong게임 (IOI14_game)C++17
0 / 100
6 ms9176 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; const int MAX_N = 1500 + 1; int n; int queried[MAX_N][MAX_N]; int par[MAX_N]; vector<int> group[MAX_N]; int remain_deg[MAX_N]; int find(int x) { return par[x] = (x == par[x] ? x : find(par[x])); } void merge(int u, int v) { u = find(u), v = find(v); if (u == v) return; if (group[u].size() > group[v].size()) swap(u, v); par[u] = v; for (int x: group[u]) group[v].push_back(x); remain_deg[v] = 0; for (int x: group[v]) { for (int i=0; i<n; ++i) { if (find(i) != v && queried[find(i)][x] != 0) { remain_deg[v]++; } } } // cout << u << ' ' << v << ' ' << remain_deg[v] << endl; } void initialize(int N) { n = N; memset(queried, -1, sizeof queried); iota(par, par+n, 0); for (int i=0; i<n; ++i) group[i].push_back(i); fill(remain_deg, remain_deg+n, n-1); } int hasEdge(int u, int v) { if (find(u) == find(v)) { queried[u][v] = queried[v][u] = 1; } else { if (remain_deg[find(u)] == 1 || remain_deg[find(v)] == 1) { queried[u][v] = queried[v][u] = 1; merge(u, v); } else { queried[u][v] = queried[v][u] = 0; remain_deg[find(u)]--; remain_deg[find(v)]--; } } return queried[u][v]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...