Submission #1090889

#TimeUsernameProblemLanguageResultExecution timeMemory
1090889owoovoTowns (IOI15_towns)C++17
13 / 100
19 ms1116 KiB
#include "towns.h" #include<bits/stdc++.h> #define ll long long #define F first #define S second using namespace std; const ll maxn=1e18; ll to0[120],tor1[120],tor2[120],gf[120][120],n; ll r1,r2; int getd(int a,int b){ return gf[a][b]; } struct DSU{ int val[120],sz[120]; void init(){ for(int i=0;i<n;i++)val[i]=i,sz[i]=1; return; } int f(int a){ if(a==val[a])return a; val[a]=f(val[a]); return val[a]; } void onion(int a,int b){ a=f(a); b=f(b); if(a==b)return; if(sz[a]>sz[b])swap(a,b); val[a]=b; sz[b]+=sz[a]; return; } }dsu; int hubDistance(int N, int sub) { n=N; for(int i=0;i<N;i++){ for(int j=i+1;j<N;j++){ gf[i][j]=getDistance(i,j); gf[j][i]=gf[i][j]; } } for(int i=1;i<N;i++)to0[i]=getd(0,i); ll maxn=0,pos=0; for(int i=0;i<N;i++){ if(to0[i]>maxn){ maxn=to0[i]; pos=i; } } r1=pos; for(int i=0;i<N;i++)tor1[i]=getd(r1,i); maxn=0,pos=0; for(int i=0;i<N;i++){ if(tor1[i]>maxn){ maxn=tor1[i]; pos=i; } } r2=pos; vector<pair<ll,ll>> vc; for(int i=0;i<N;i++){ ll dis=(to0[r1]+tor1[i]-to0[i])/2; vc.push_back({dis,tor1[i]-dis}); } ll ans=maxn; for(int i=0;i<N;i++){ ans=min(ans,max(vc[i].F,tor1[r2]-vc[i].F)); } vector<ll> want; for(int i=0;i<N;i++){ if(ans==max(vc[i].F,tor1[r2]-vc[i].F)){ want.push_back(vc[i].F); } } int ok=0; for(auto dis:want){ int s=0,m=0,l=0; vector<int> now; for(int i=0;i<N;i++){ if(vc[i].F<dis)s++; else if(vc[i].F==dis)now.push_back(i); else l++; } if(s>N/2||l>N/2)continue; int nx=now[0],mis=1,OK=1; dsu.init(); for(int i=1,x=now[i];i<now.size();i++,x=now[i]){ if(nx==0){ mis=1; nx=now[0]; continue; } if(getd(nx,x)<vc[nx].S+vc[x].S){ dsu.onion(nx,x); mis++; }else{ mis--; } if(mis==0)nx=0; } for(int i=0,x=now[i];i<now.size();i++,x=now[i]){ if(x==dsu.f(x)){ if(getd(nx,x)<vc[nx].S+vc[x].S){ dsu.onion(nx,x); } } } for(int i=0,x=now[i];i<now.size();i++,x=now[i]){ if(x==dsu.f(x)&&dsu.sz[x]>n/2){ OK=0; } } ok|=OK; } return ok==1?ans:-ans; }

Compilation message (stderr)

towns.cpp: In function 'int getd(int, int)':
towns.cpp:11:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   11 |  return gf[a][b];
      |         ~~~~~~~^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:43:5: warning: declaration of 'maxn' shadows a global declaration [-Wshadow]
   43 |  ll maxn=0,pos=0;
      |     ^~~~
towns.cpp:7:10: note: shadowed declaration is here
    7 | const ll maxn=1e18;
      |          ^~~~
towns.cpp:51:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   51 |  for(int i=0;i<N;i++)tor1[i]=getd(r1,i);
      |                                   ^~
towns.cpp:87:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(int i=1,x=now[i];i<now.size();i++,x=now[i]){
      |                        ~^~~~~~~~~~~
towns.cpp:101:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   for(int i=0,x=now[i];i<now.size();i++,x=now[i]){
      |                        ~^~~~~~~~~~~
towns.cpp:108:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   for(int i=0,x=now[i];i<now.size();i++,x=now[i]){
      |                        ~^~~~~~~~~~~
towns.cpp:77:11: warning: unused variable 'm' [-Wunused-variable]
   77 |   int s=0,m=0,l=0;
      |           ^
towns.cpp:115:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  115 |  return ok==1?ans:-ans;
      |         ~~~~~^~~~~~~~~
towns.cpp:34:28: warning: unused parameter 'sub' [-Wunused-parameter]
   34 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...