# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
909758 | 2024-01-17T11:49:45 Z | Wansur | Towns (IOI15_towns) | C++14 | 14 ms | 1116 KB |
#include <bits/stdc++.h> #define f first #define s second #define ent '\n' #pragma once using namespace std; typedef long long ll; const int mx=212; int p[mx]; int sz[mx]; int d[mx][mx]; bool was[mx][mx]; int cnt; int getDistance(int i, int j); void upd(int i,int j){ if(was[i][j])return; was[i][j]=was[j][i]=1; cnt++; d[i][j]=d[j][i]=getDistance(i,j); } int get(int x){ if(p[x]==x)return x; return p[x]=get(p[x]); } void merge(int a,int b){ if(get(a)==get(b))return; sz[get(b)]+=sz[get(a)]; p[get(a)]=get(b); } int hubDistance(int n, int sub){ cnt=0; for(int i=0;i<n;i++){ p[i]=i; sz[i]=1; for(int j=0;j<n;j++){ was[i][j]=0; d[i][j]=-1; if(i==j){ was[i][j]=1; d[i][j]=0; } } } int v=0,u=0; for(int i=1;i<n;i++){ upd(0,i); if(d[0][i]>d[0][v]){ v=i; } } for(int i=0;i<n;i++){ upd(v,i); if(d[v][i]>d[v][u]){ u=i; } } for(int i=0;i<n;i++){ upd(u,i); } int ans=2e9; int mid=0; for(int i=0;i<n;i++){ int t=d[v][i]+d[i][u]-d[v][u]; ans=min(ans,max(d[v][i],d[i][u])-t/2); if(ans==max(d[v][i],d[i][u])-t/2){ mid=d[v][i]-t/2; } } if(sub==3 || sub==1){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ upd(i,j); } } int c1=0,c2=0,c3=0; vector<pair<int,int>> ord; for(int i=0;i<n;i++){ int t=(d[v][i]+d[i][u]-d[v][u]); if(d[v][i]-t/2<mid)c1++; else if(d[v][i]-t/2==mid){ ord.push_back({i,t/2}); } else c3++; } for(auto x:ord){ for(auto y:ord){ ll v=x.f,u=y.f,dist=x.s+y.s; if(dist!=d[v][u]){ merge(v,u); } } } set<int> s; for(auto x:ord){ s.insert(get(x.f)); } for(auto v:s){ c2=max(c2,sz[v]); } if(max({c1,c2,c3})>n/2)ans*=-1; assert(cnt<=n*(n-1)/2); return ans; } int c1=0,c2=0,c3=0; for(int i=0;i<n;i++){ int t=(d[v][i]+d[i][u]-d[v][u]); if(d[v][i]-t/2<mid)c1++; else if(d[v][i]-t/2==mid)c2++; else c3++; } if(max({c1,c2,c3})>n/2)ans*=-1; return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 960 KB | Output is correct |
2 | Correct | 9 ms | 860 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 14 ms | 1116 KB | Output is correct |
5 | Correct | 14 ms | 1116 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 1116 KB | Output is correct |
2 | Correct | 9 ms | 860 KB | Output is correct |
3 | Correct | 12 ms | 964 KB | Output is correct |
4 | Correct | 12 ms | 1116 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 10 ms | 860 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 1116 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 860 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 860 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |