제출 #159283

#제출 시각아이디문제언어결과실행 시간메모리
159283oolimry게임 (IOI14_game)C++14
100 / 100
515 ms17016 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; class UFDS { typedef vector<int> vi; public: vi p, rak, setSize; int numSets; void create(int n){ setSize.assign(n, 1); numSets = n; rak.assign(n, 0); p.assign(n, 0); for(int i =0;i < n;i++){ p[i] = i; } } int findSet(int i){ return (p[i] == i) ? i : (p[i] = findSet(p[i])); } bool isSameSet(int i, int j){ return findSet(i) == findSet(j); } void unionSet(int i, int j){ if(isSameSet(i,j)) return; numSets--; int x = findSet(i); int y = findSet(j); if(rak[x] > rak[y]) { p[y] = x; setSize[x] += setSize[y]; } else { p[x] = y; setSize[y] += setSize[x]; if(rak[x] == rak[y]) rak[y]++; } } }; UFDS uf; typedef pair<int,int> ii; static int m[5000000]; int N; int mii(int x, int y){ if(x > y) swap(x,y); return x * 2000 + y; } void initialize(int n) { uf.create(n); N = n; for(int i = 0;i < n;i++){ for(int j = i+1;j < n;j++){ m[mii(i,j)] = 1; } } } int hasEdge(int u, int v) { if(uf.isSameSet(u,v)){ return 0; } int x = uf.findSet(u); int y = uf.findSet(v); if(m[mii(x,y)] == 1){ uf.unionSet(u,v); for(int i = 0;i < N;i++){ int w = i; int z = uf.findSet(u); m[mii(w,z)] = m[mii(w,x)] + m[mii(w,y)]; } return 1; } else{ m[mii(x,y)]--; return 0; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...