Submission #296361

#	Time	Username	Problem	Language	Result	Execution time	Memory
296361		thebes	Towns (IOI15_towns)	C++14	10 / 100	27 ms	768 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
#define F first
#define S second

const int MN = 111;
int A, B, C, R, i, j, cnt, rev[MN], pre[MN], suf[MN], dis[2][MN], ds[MN], mat[MN][MN];
map<int,int> mp; vector<pii> vec[MN];
vector<vector<pii>> go; vi ok;
int fnd(int x){return ds[x]=x==ds[x]?x:fnd(ds[x]);}

int hubDistance(int N, int sub) {
	dis[0][0] = 0;
	A = B = 0; mp.clear(); cnt = 0;
	for(i=1;i<N;i++){
        dis[0][i] = getDistance(A, i);
        if(dis[0][i]>dis[0][B]) B = i;
	}
	dis[1][0] = dis[0][B];
	C = 0;
	for(i=1;i<N;i++){
        if(i==B) continue;
        dis[1][i] = getDistance(B, i);
        int ex = (dis[1][i]+dis[0][i]-dis[0][B])/2;
        mp[dis[1][i]-ex] = 0;
        if(dis[1][i]>dis[1][C]) C = i;
	}
	int D = dis[1][C];
	for(auto it=mp.begin();it!=mp.end();it++){
        it->second = ++cnt;
        rev[cnt] = it->first;
        vec[cnt].clear();
	}
	for(i=1;i<N;i++){
        if(i==B) continue;
        int ex = (dis[1][i]+dis[0][i]-dis[0][B])/2;
        vec[mp[dis[1][i]-ex]].push_back({i, ex});
	}
	R = dis[0][B];
	pre[0] = 1; suf[cnt+1] = 1;
	for(i=1;i<=cnt;i++){
        R = min(R, max(rev[i], D-rev[i]));
        pre[i] = vec[i].size()+pre[i-1];
	}
	for(i=cnt;i>=1;i--) suf[i] = vec[i].size()+suf[i+1];
	ok.clear();
	for(i=1;i<=cnt;i++){
        if(max(rev[i], D-rev[i])==R){
            if(pre[i-1]*2<=N&&suf[i+1]*2<=N)
                ok.push_back(i);
        }
	}
	if(ok.size()==0) return -R;
	else if(ok.size()==1){
        go.clear(); memset(mat,-1,sizeof(mat));
        int rt = ok[0];
        for(auto v : vec[rt]){
            go.push_back(vector<pii>());
            go.back().push_back(v);
        }
        for(i=1;i<=N;i++) ds[i] = i;
        while(go.size()>=2){
            vector<pii> a, b, c;
            a = go[0], b = go[1];
            go.erase(go.begin(),go.begin()+2);
            if(getDistance(a[0].F,b[0].F)==a[0].S+b[0].S){
                mat[fnd(a[0].F)][fnd(b[0].F)]=0;
                mat[fnd(b[0].F)][fnd(a[0].F)]=0;
                int k = min(a.size(),b.size());
                for(int i=k;i<(int)a.size();i++) c.push_back(a[i]);
                for(int i=k;i<(int)b.size();i++) c.push_back(b[i]);
                if(c.size()) go.push_back(c);
            }
            else{
                for(int i=0;i<N;i++) mat[fnd(a[0].F)][i]=max(mat[fnd(a[0].F)][i],mat[fnd(b[0].F)][i]);
                ds[fnd(b[0].F)] = fnd(a[0].F);
                for(auto v : b) a.push_back(v);
                go.push_back(a);
            }
        }
        if(go.empty()) return -R;
        int cand = go[0][0].F, len = go[0][0].S;
        cnt = 0;
        for(auto v : vec[rt]){
            if(fnd(v.F)==fnd(cand)) cnt++;
            else if(mat[fnd(v.F)][fnd(cand)]==-1){
                if(getDistance(v.F,cand)!=len+v.S){
                    cnt++;
                    for(int i=0;i<N;i++) mat[fnd(cand)][i]=max(mat[fnd(cand)][i],mat[fnd(v.F)][i]);
                }
                else mat[fnd(v.F)][fnd(cand)]=mat[fnd(cand)][fnd(v.F)]=0;
            }
        }
        if(2*cnt<=N) return R;
        else return -R;
	}
	else{
        assert(false);
	}
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:47:31: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   47 |         pre[i] = vec[i].size()+pre[i-1];
      |                  ~~~~~~~~~~~~~^~~~~~~~~
towns.cpp:49:44: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   49 |  for(i=cnt;i>=1;i--) suf[i] = vec[i].size()+suf[i+1];
      |                               ~~~~~~~~~~~~~^~~~~~~~~
towns.cpp:73:28: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
   73 |                 int k = min(a.size(),b.size());
      |                         ~~~^~~~~~~~~~~~~~~~~~~
towns.cpp:74:25: warning: declaration of 'i' shadows a global declaration [-Wshadow]
   74 |                 for(int i=k;i<(int)a.size();i++) c.push_back(a[i]);
      |                         ^
towns.cpp:11:17: note: shadowed declaration is here
   11 | int A, B, C, R, i, j, cnt, rev[MN], pre[MN], suf[MN], dis[2][MN], ds[MN], mat[MN][MN];
      |                 ^
towns.cpp:75:25: warning: declaration of 'i' shadows a global declaration [-Wshadow]
   75 |                 for(int i=k;i<(int)b.size();i++) c.push_back(b[i]);
      |                         ^
towns.cpp:11:17: note: shadowed declaration is here
   11 | int A, B, C, R, i, j, cnt, rev[MN], pre[MN], suf[MN], dis[2][MN], ds[MN], mat[MN][MN];
      |                 ^
towns.cpp:79:25: warning: declaration of 'i' shadows a global declaration [-Wshadow]
   79 |                 for(int i=0;i<N;i++) mat[fnd(a[0].F)][i]=max(mat[fnd(a[0].F)][i],mat[fnd(b[0].F)][i]);
      |                         ^
towns.cpp:11:17: note: shadowed declaration is here
   11 | int A, B, C, R, i, j, cnt, rev[MN], pre[MN], suf[MN], dis[2][MN], ds[MN], mat[MN][MN];
      |                 ^
towns.cpp:93:29: warning: declaration of 'i' shadows a global declaration [-Wshadow]
   93 |                     for(int i=0;i<N;i++) mat[fnd(cand)][i]=max(mat[fnd(cand)][i],mat[fnd(v.F)][i]);
      |                             ^
towns.cpp:11:17: note: shadowed declaration is here
   11 | int A, B, C, R, i, j, cnt, rev[MN], pre[MN], suf[MN], dis[2][MN], ds[MN], mat[MN][MN];
      |                 ^
towns.cpp:16:28: warning: unused parameter 'sub' [-Wunused-parameter]
   16 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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