제출 #422133

#제출 시각아이디문제언어결과실행 시간메모리
422133daanolav게임 (IOI14_game)C++14
0 / 100
13 ms23760 KiB
#include "game.h" #include <vector> using namespace std; #define MAXN 1000001 typedef vector<int> vi; int n; int ufParent[MAXN]; int ufSize[MAXN]; int ufLinkingPossibilities[MAXN]; vi ufPossibleConnections[MAXN]; int ufFind(int a) { if(ufParent[a] == a) { return a; } ufParent[a] = ufFind(ufParent[a]); return ufParent[a]; } void ufUnite(int a, int b) { a = ufFind(a); b = ufFind(b); if(ufSize[a] > ufSize[b]) { swap(a,b); } ufParent[b] = a; ufSize[a] += ufSize[b]; for(int i = 0; i < n; ++i) { if(i == a || i == b) { //ufLinkingPossibilities[a] -= ufPossibleConnections[a][i]; ufPossibleConnections[a][i] = 0; } else { ufPossibleConnections[a][i] += ufPossibleConnections[b][i]; //ufLinkingPossibilities[a] += ufPossibleConnections[b][i]; ufPossibleConnections[i][a] += ufPossibleConnections[i][b]; ufPossibleConnections[i][b] = 0; } } } void initialize(int n) { ::n = n; for(int i = 0; i < n; ++i) { ufParent[i] = i; ufSize[i] = 1; ufLinkingPossibilities[i] = 0; for(int j = 0; j < n; ++j) { if(i == j) { ufPossibleConnections[i].push_back(0); continue; } ufPossibleConnections[i].push_back(1); ufLinkingPossibilities[i] += 1; } } } int hasEdge(int u,int v) { if(ufPossibleConnections[ufFind(u)][ufFind(v)] > 1) { return 0; } else { ufUnite(u,v); return 1; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...