Submission #799210

#	Time	Username	Problem	Language	Result	Execution time	Memory
799210		I_Love_EliskaM_	Towns (IOI15_towns)	C++14	48 / 100	1075 ms	1112 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
const int inf=1e9+9;

const int _N=555;
int d[_N][_N];

int p1(int n) {
  
  int mx=0; 
  int f,s;
  forn(i,n) {
    if (!i) continue;
    int x=getDistance(0,i);
    if (x>mx) {
      mx=x;
      f=i;
    }
  }

  vector<int> a(n), b(n);
  mx=0;
  forn(i,n) {
    if (i==f) continue;
    int x=getDistance(f,i);
    a[i]=x;
    if (x>mx) {
      mx=x;
      s=i;
    }
  }
  forn(i,n) {
    if (i==s) continue;
    int x=getDistance(s,i);
    b[i]=x;
  }

  int ans=inf;

  map<int,int> cnt;

  set<int> s1,s2;

  forn(i,n) {
    if (i==f || i==s) continue;
    int x=a[i], y=b[i], z=a[s];
    int A=(x-y+z)/2;
    int B=z-A;
    int C=x-A;
    ans=min(ans,max(A,B));
    cnt[A]++;
    s1.insert(A), s2.insert(B);
  }
  vector<int> x,y;
  for(auto&t:s1) x.pb(t);
  for(auto&t:s2) y.pb(t);
  reverse(all(y));
  int left=1;
  forn(i,s1.size()) {
    if (max(x[i],y[i])==ans) {
      int a=left, b=cnt[x[i]];
      int c=n-a-b;
      if (max({a,b,c})<=n/2) return ans;
    }
    left+=cnt[x[i]];
  }
  return -ans;

}

struct DSU {
  vector<int> p,sz;
  DSU(int n) {forn(i,n)p.pb(i),sz.pb(1);}
  int get(int u) {return p[u]==u?u:get(p[u]);}
  void uni(int u, int v){
    u=get(u),v=get(v); if (u==v)return; if (sz[u]<sz[v]) swap(u,v);
    p[v]=u;sz[u]+=sz[v];
  }
};

int p3(int n) {

  forn(i,n) {
    forn(j,i) {
      int x=getDistance(i,j);
      d[i][j]=d[j][i]=x;
    }
  }

  int f=0,s=0;
  forn(i,n) if (d[0][i]>d[0][f]) f=i;
  forn(i,n) if (d[f][i]>d[f][s]) s=i;

  int ans=inf;
  map<int,int> cnt;
  map<int,vector<int>> q;
  vector<int> ok(n);
  set<int> s1,s2;
  forn(i,n) {
    if (i==f || i==s) continue;
    int x=d[f][i], y=d[s][i], z=d[f][s];
    int A=(x-y+z)/2;
    int B=z-A;
    int C=x-A;
    ans=min(ans,max(A,B));
    ok[i]=C;
    cnt[A]++;
    q[A].pb(i);
    s1.insert(A), s2.insert(B);
  }

  int left=1;
  vector<int> x,y;
  for(auto&t:s1)x.pb(t);
  for(auto&t:s2)y.pb(t);
  reverse(all(y));
  forn(i,s1.size()) {
    if (max(x[i],y[i])==ans) {
      int right=n-left-cnt[x[i]];
      int mx=max(left,right);
      DSU dsu(n);
      for(auto&u:q[x[i]]) {
        for(auto&v:q[x[i]]) {
          int dist = d[u][v];
          if (dist < ok[u]+ok[v]) dsu.uni(u,v);
        }
      }
      forn(j,n) mx=max(mx,dsu.sz[j]);
      if (mx<=n/2) return ans;
    }
    left+=cnt[x[i]];
  }

  return -ans;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int p5(int n) {

  int f=0,s=0;
  int lim=5*n;
  forn(i,n) {
    if (i==0) continue; --lim;
    d[0][i]=d[i][0]=getDistance(i,0);
    if (d[0][i] > d[0][f]) f=i;
  }
  forn(i,n) {
    if (i==0 || i==f) continue; --lim;
    d[f][i]=d[i][f]=getDistance(i,f);
    if (d[f][i] > d[f][s]) s=i;
  }

  map<int,vector<int>> pos;
  map<int,int> cnt;
  set<int> X,Y;

  vector<int> di(n);
  int ans=inf;

  forn(i,n) {
    if (i==0 || i==f || i==s) continue; --lim;
    d[s][i]=d[i][s]=getDistance(i,s);

    int a=d[f][i], b=d[s][i], c=d[f][s];
    int x = (a-b+c)/2;
    int y = c-x;
    int z = a-x;
    X.insert(x), Y.insert(y);
    di[i]=z;
    cnt[x]++;
    pos[x].pb(i);

    ans=min(ans,max(x,y));
  }

  int l=1;
  vector<int> x,y;
  for(auto&v:X) x.pb(v);
  for(auto&v:Y) y.pb(v);
  reverse(all(y));
  
  forn(i,x.size()) {
    int r=n-l-cnt[x[i]];
    if (max(x[i],y[i])==ans) {
      if (max({l,r,cnt[x[i]]})<=n/2) return ans;
      vector<pi> asked;
      map<pi,int> was;
      int T=pos[x[i]].size();
      DSU dsu(n);
      forn(it,lim) {
        int a=rng()%T, b=rng()%T;
        int u=pos[x[i]][a], v=pos[x[i]][b];
        if (dsu.get(u)==dsu.get(v)) {
          --it;
          continue;
        }
        if (was[{u,v}]) {
          --it;
          continue;
        }
        int X=getDistance(u,v), Y=di[u], Z=di[v];
        if (X < Y+Z) {
          dsu.uni(u,v);
          asked.pb({u,v});
          for(auto&it:asked) {
            int A=dsu.get(it.f), B=dsu.get(it.s);
            was[{A,B}]=1;
            was[{B,A}]=1;
          }
        }
      }
      int mx=max({l,r});
      for(auto&v:dsu.sz) mx=max(mx,v);
      if (mx<=n/2) return ans;
    }
    l+=cnt[x[i]];
  }
  return -ans;

}

int hubDistance(int n, int sub) {
  if (sub<=2 || sub==4) return p1(n);
  if (sub==3) return p3(n);
  if (sub==5) return p5(n);
  return 0;
}

Compilation message (stderr)

towns.cpp: In function 'int p1(int)':
towns.cpp:56:9: warning: unused variable 'C' [-Wunused-variable]
   56 |     int C=x-A;
      |         ^
towns.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for(int i=0;i<n;++i)
......
   66 |   forn(i,s1.size()) {
      |        ~~~~~~~~~~~              
towns.cpp:66:3: note: in expansion of macro 'forn'
   66 |   forn(i,s1.size()) {
      |   ^~~~
towns.cpp:68:11: warning: declaration of 'a' shadows a previous local [-Wshadow]
   68 |       int a=left, b=cnt[x[i]];
      |           ^
towns.cpp:28:15: note: shadowed declaration is here
   28 |   vector<int> a(n), b(n);
      |               ^
towns.cpp:68:19: warning: declaration of 'b' shadows a previous local [-Wshadow]
   68 |       int a=left, b=cnt[x[i]];
      |                   ^
towns.cpp:28:21: note: shadowed declaration is here
   28 |   vector<int> a(n), b(n);
      |                     ^
towns.cpp: In function 'int p3(int)':
towns.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for(int i=0;i<n;++i)
......
  124 |   forn(i,s1.size()) {
      |        ~~~~~~~~~~~              
towns.cpp:124:3: note: in expansion of macro 'forn'
  124 |   forn(i,s1.size()) {
      |   ^~~~
towns.cpp: In function 'int p5(int)':
towns.cpp:150:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  150 |     if (i==0) continue; --lim;
      |     ^~
towns.cpp:150:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  150 |     if (i==0) continue; --lim;
      |                         ^~
towns.cpp:155:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  155 |     if (i==0 || i==f) continue; --lim;
      |     ^~
towns.cpp:155:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  155 |     if (i==0 || i==f) continue; --lim;
      |                                 ^~
towns.cpp:168:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  168 |     if (i==0 || i==f || i==s) continue; --lim;
      |     ^~
towns.cpp:168:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  168 |     if (i==0 || i==f || i==s) continue; --lim;
      |                                         ^~
towns.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for(int i=0;i<n;++i)
......
  189 |   forn(i,x.size()) {
      |        ~~~~~~~~~~               
towns.cpp:189:3: note: in expansion of macro 'forn'
  189 |   forn(i,x.size()) {
      |   ^~~~
towns.cpp:195:27: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  195 |       int T=pos[x[i]].size();
      |             ~~~~~~~~~~~~~~^~
towns.cpp:198:20: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  198 |         int a=rng()%T, b=rng()%T;
      |               ~~~~~^~
towns.cpp:198:31: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  198 |         int a=rng()%T, b=rng()%T;
      |                          ~~~~~^~
towns.cpp:208:13: warning: declaration of 'X' shadows a previous local [-Wshadow]
  208 |         int X=getDistance(u,v), Y=di[u], Z=di[v];
      |             ^
towns.cpp:162:12: note: shadowed declaration is here
  162 |   set<int> X,Y;
      |            ^
towns.cpp:208:33: warning: declaration of 'Y' shadows a previous local [-Wshadow]
  208 |         int X=getDistance(u,v), Y=di[u], Z=di[v];
      |                                 ^
towns.cpp:162:14: note: shadowed declaration is here
  162 |   set<int> X,Y;
      |              ^
towns.cpp:212:20: warning: declaration of 'it' shadows a previous local [-Wshadow]
  212 |           for(auto&it:asked) {
      |                    ^~
towns.cpp:197:12: note: shadowed declaration is here
  197 |       forn(it,lim) {
      |            ^~
towns.cpp:4:27: note: in definition of macro 'forn'
    4 | #define forn(i,n) for(int i=0;i<n;++i)
      |                           ^
towns.cpp: In function 'int p1(int)':
towns.cpp:52:18: warning: 'second' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |     if (i==f || i==s) continue;
      |                  ^
towns.cpp:52:10: warning: 'first' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |     if (i==f || i==s) continue;
      |          ^

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39