Submission #298921

#TimeUsernameProblemLanguageResultExecution timeMemory
298921lakshith_Game (IOI14_game)C++14
15 / 100
1 ms512 KiB
#include <bits/stdc++.h> #include "game.h" #define shit cout << "shit\n"; using namespace std; struct subset{ int parent; int rank; }; subset subsets[1510]; int n; int find(int x){ if(subsets[x].parent==x)return x; subsets[x].parent = find(subsets[x].parent); return subsets[x].parent; } void Union(int X,int Y){ int x = find(X); int y = find(Y); if(subsets[x].rank<subsets[y].rank){ subsets[x].parent = y; }else if(subsets[x].rank>subsets[y].rank){ subsets[y].parent = x; }else{ subsets[x].parent = y; subsets[y].rank++; } find(X); find(Y); } bool flag[1501][1501]; void initialize(int N) { n=N; for(int i=0;i<n;i++){ subsets[i] = {i,1}; } } bool getRemaining(int u,int v){ vector<int> u_set,v_set; int U =find(u),V = find(v); for(int i=0;i<n;i++){ // int p = find(i); int p = subsets[i].parent; if(p==U)u_set.push_back(i); if(p==V)v_set.push_back(i); } int C = 0; // for(int a:u_set) // cout << a << "\t"; // cout << endl; // for(int b:v_set) // cout << b << "\t"; // cout << endl; for(int a:u_set){ for(int b:v_set){ if(!flag[a][b])C++; if(C>=2)return false; } } return true; } int hasEdge(int u, int v) { int r = 0; if(getRemaining(u,v))r=1; flag[u][v] =flag[v][u] = true; if(r==1) Union(u,v); return r; } // int main(){ // int n,r; // cin >> n >> r; // initialize(n); // for(int i=0;i<r;i++){ // int a,b; // cin >> a >> b; // cout << hasEdge(a,b) << "\n"; // } // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...