제출 #641427

#제출 시각아이디문제언어결과실행 시간메모리
641427MasterTaster게임 (IOI14_game)C++14
100 / 100
657 ms78012 KiB
#include <iostream> #include <set> #include "game.h" #define pb push_back #define ll long long #define pii pair<int, int> #define xx first #define yy second using namespace std; int dsu[1510], rnk[1510], n, cnt[1510][1510]; set<pii> svi; int root(int u) { while (u!=dsu[u]) { dsu[u]=dsu[dsu[u]]; u=dsu[u]; } return u; } void connect(int ru, int rv) { //if (root(u)==root(v)) return; if (rnk[ru]<=rnk[rv]) { if (rnk[ru]==rnk[rv]) rnk[rv]++; dsu[ru]=rv; } else dsu[rv]=ru; int r=root(ru); int pr=ru+rv-r; ///cout<<ru<<"+"<<rv<<"->"<<r<<endl; for (int i=0; i<n; i++) { cnt[i][r]+=cnt[i][pr]; cnt[r][i]+=cnt[i][pr]; } } void initialize(int N) { n=N; for (int i=0; i<n; i++) for (int j=0; j<n; j++) { if (i<j) svi.insert({i, j}); cnt[i][j]=1; } for (int i=0; i<n; i++) { dsu[i]=i; rnk[i]=1; } } void out() { for (int i=0; i<n; i++) { for (int j=0; j<n; j++) if (i!=j) cout<<cnt[i][j]<<" "; else cout<<-1<<" "; cout<<endl; } } int hasEdge(int u, int v) { if (u>v) swap(u, v); int ru, rv; ru=root(u); rv=root(v); if (ru==rv) return 1; if (cnt[ru][rv]>1) { cnt[ru][rv]--; cnt[rv][ru]--; return 0; } else { connect(ru, rv); //out(); return 1; } /*svi.erase({u, v}); bool moze=true; for (auto par:svi) { int a, b; a=par.xx; b=par.yy; //cout<<a<<" "<<b<<" "<<root(a)<<" "<<root(b)<<" "<<ru<<" "<<rv<<endl; if ((root(a)==ru && root(b)==rv) || (root(a)==rv && root(b)==ru)) { moze=false; break; } } if (!moze) return 0; connect(u, v); return 1;*/ }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...