Submission #348389

#TimeUsernameProblemLanguageResultExecution timeMemory
348389iliccmarkoGame (IOI14_game)C++14
15 / 100
1 ms492 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define endl "\n" #define INF 1000000000 #define LINF 1000000000000000LL #define pb push_back #define all(x) x.begin(), x.end() #define len(s) (int)s.size() #define test_case { int t; cin>>t; while(t--)solve(); } #define single_case solve(); #define line cerr<<"----------"<<endl; #define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL); } #define mod 1000000007LL int n; const int N = 1505; int parent[N], s[N]; int cnt[N][N]; inline int find_parent(int u) { if(parent[u]==u) return u; return parent[u] = find_parent(parent[u]); } inline void _union(int u, int v) { u = find_parent(u); v = find_parent(v); if(u!=v) { if(s[u]<s[v]) swap(u, v); for(int i = 1;i<=n;i++) { cnt[i][u] += cnt[i][v]; } parent[v] = u; s[u] += s[v]; } } void initialize(int N) { n = N; for(int i = 1;i<=n;i++) parent[i] = i, s[i] = 1; } int hasEdge(int u, int v) { u++; v++; int a = find_parent(u); int b = find_parent(v); int w = s[a]*s[b]; for(int i = 1;i<=n;i++) { if(parent[i]==b) w -= cnt[i][a]; } //cout<<u<<" "<<v<<" "<<a<<" "<<b<<" "<<w<<endl; cnt[u][b]++; cnt[v][a]++; if(w==1) { _union(a, b); return 1; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...