Submission #123454

#TimeUsernameProblemLanguageResultExecution timeMemory
123454ekremGame (IOI14_game)C++98
42 / 100
1074 ms3660 KiB
#include <bits/stdc++.h> #include "game.h" #define st first #define nd second #define mp make_pair #define pb push_back #define mod 1000000007 #define N 1505 using namespace std; typedef long long ll; int n, ata[N], sz[N], deg[N], of[N][N], vis[N]; int atabul(int x){return ata[x] = (ata[x] == x)?x:atabul(ata[x]);} void merge(int x, int y){ int xx = atabul(x); int yy = atabul(y); if(xx != yy){ ata[xx] = yy; sz[yy] += sz[xx]; // if(sz[yy] == n){ // cout << "OF MKAKAKKKF" << endl; // } } } void initialize(int nn){ n = nn; for(int i = 1; i <= n; i++){ ata[i] = i; sz[i] = 1; } } void dfs(int node){ vis[node] = 1; for(int i = 1; i <= n; i++) if(!vis[i] and of[node][i] == 0) dfs(i); } int hasEdge(int u, int v){u++;v++; int xx = atabul(u); int yy = atabul(v); if(sz[xx] + sz[yy] == n){ of[u][v] = 1; of[v][u] = 1; return 0; } of[u][v] = 1; of[v][u] = 1; memset(vis, 0, sizeof vis); dfs(u); if(!vis[v]){ of[u][v] = 0; of[v][u] = 0; merge(xx, yy); return 1; } of[u][v] = 1; of[v][u] = 1; return 0; } // int read_int() { // int x; // assert(scanf("%d", &x) == 1); // return x; // } // int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // int n, u, v; // n = read_int(); // initialize(n); // for (int i = 0; i < n * (n - 1) / 2; i++) { // u = read_int(); // v = read_int(); // printf("%d\n", hasEdge(u, v)); // } // // for(int i = 1; i <= n; i++) // // cout << i << " " << deg[i] << endl; // return 0; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...