Submission #730791

#	Time	Username	Problem	Language	Result	Execution time	Memory
730791		Vu_CG_Coder	Towns (IOI15_towns)	C++14	35 / 100	28 ms	24396 KiB

towns

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

int f[110][110];
// int getDistance(int x , int y){
//     return f[x][y];
// }

int sub1(int N,int sub){
    int n = N;
    pair <int,int> tmp;
    vector <int> val , value;
    val.assign(n,0);
    value.assign(n,0);
    for (int i = 1 ; i < n ; i++){
        int x = getDistance(0,i);
        tmp = max(tmp,make_pair(x,i));
    }

    int u = tmp.second;
    tmp.first = 0;
    for (int i = 0 ; i < n ; i++)
    if (i != u){
        int x = getDistance(i,u);
        val[i] = x;
        tmp = max(tmp,make_pair(x,i));
    }
    int v = tmp.second;
    int R = 1e9;
    //cout << u << " " << v << "\n";

    for (int i = 0 ; i < n ; i++)
    if (i != u && i != v){
        int x = getDistance(v,i);
        value[i] = x;
        int y = val[i];
        int z = val[v];
        int a = (x + y - z)/2;
        int b = x - a;
        int c = z - b;
        int r = max(a,max(b,c));

        if (r < R){
            tmp = make_pair(b,c);
            R = r;
        }
    }

    if (sub < 3) return R;

  //  cout << tmp.first << " " << tmp.second << "\n";

    int cntu = 1 , cntv = 1 , cnt = 0;
    for (int i = 0 ; i < n ; i++) 
    if (i != u && i != v) 
    {
        int x = val[i];
        int y = val[v];
        int z = value[i];
        int a = (x + y - z)/2;

    //    cout << i << " " << a << '\n';
        
        if (a < tmp.second) cntu++;
        if (a == tmp.second) cnt++;
        if (a > tmp.second) cntv++;
    }

 //  cout << cntu << " " << cntv << " " << cnt << "\n";

    if (cntu > n/2 || cntv > n/2 || cnt > n/2) return -R;
    return R; 
}

vector <pair<int,int> > adj[510];
vector <pair<int,int> > dis[510] ,pos[1000010];
int cnt = 0;
int tk[510] = {0};

int dfs(int u , int par){
    int res = 0;
    for (pair <int,int> v : adj[u])
    if (v.first != par){
       // cout << v.first << " " << v.second << "\n";
       int x = dfs(v.first,u);
       res = max(res,x + v.second); 
    }
    return res;
}

int DFS(int u, int par, int t,int n){
    int d = (u < n);
    tk[u] = 1;
    for (pair<int,int> v : adj[u])
    if (v.first != par && v.first != t){
        d += DFS(v.first,u,t,n);
    }
    return d;
}

int sub3(int n){
    for (int i = 0 ; i <= 500 ; i++){
        adj[i].clear();
        dis[i].clear();
    }

    vector <vector<int> > val;
    vector <int> value;
    int m = n;
    val.assign(n,vector<int>(n,0));
    for (int i = 0 ; i < n ; i++)
        for (int j = i + 1; j < n ; j++) {
            int x = getDistance(i,j);
            val[i][j] = x;
            val[j][i] = x;
        }

    pair<int,int> tmp(1e9,1e9);

    for (int i = 1 ; i < n ; i++)
        for (int j = i + 1 ; j < n ; j++){
        int x = val[i][j];
        int y = val[0][i];
        int z = val[0][j];
        int a = (x + y - z)/2;
        int b = x - a;
        int c = z - b;

        int ok = 0;
        for (pair<int,int> v : pos[c]){ //cout << v.first << " " << v.second << "\n";
            if (val[v.first][0] - c + val[i][0] - c == val[v.first][i] || 
                val[v.first][0] - c + val[j][0] - c == val[v.first][j]){
                ok = v.second;
                break;
            }
        }

      //  cout << i << " " << j << " " << a << " " << b << " " << c << " " << ok << "\n";

        if (!ok)
        {
            ok = m++;
            pos[c].push_back(make_pair(i,ok));
            value.push_back(c);
        } 

        dis[i].push_back(make_pair(a,ok));
        dis[j].push_back(make_pair(b,ok));
        tmp = min(tmp,make_pair(c,ok));
    }

    dis[0].push_back(tmp);

    for (int i = 0 ; i < n ; i++){
        sort(dis[i].begin(),dis[i].end());
        dis[i].resize(unique(dis[i].begin(),dis[i].end()) - dis[i].begin());

        if (!dis[i].empty()){
            adj[i].push_back(make_pair(dis[i][0].second,dis[i][0].first));
            adj[dis[i][0].second].push_back(make_pair(i,dis[i][0].first));
        }

        for (int j = 1 ; j < dis[i].size() ; j++){
            adj[dis[i][j].second].push_back(make_pair(dis[i][j - 1].second,dis[i][j].first - dis[i][j - 1].first));
            adj[dis[i][j - 1].second].push_back(make_pair(dis[i][j].second,dis[i][j].first - dis[i][j - 1].first));
        }
    }

    for (int i = 0 ; i < m; i++){
        sort(adj[i].begin(),adj[i].end());
        adj[i].resize(unique(adj[i].begin(),adj[i].end()) - adj[i].begin());

       // for (pair<int,int> v : adj[i]) cout << i << " " << v.first << "\n";
    }

    int R = 1e9 , ok = 0;
    for (int i = n ; i < m ; i++){
        int x = dfs(i,i);
      //   cout << x << " " << i << "\n";
        if (x < R){
            ok = 1;
            R = x;
            memset(tk,0,sizeof(tk));
            for (int j = 0 ; j < m ; j++)
            if (i != j && !tk[j]){
                int d = DFS(j,j,i,n);
                if (d > n/2) ok = 0;
            //    if (i == 13) cout << j << " " << d << "\n"; 
            }
        }
    }

    for (int v : value) pos[v].clear();

    if (!ok) R = -R;
    return R;
}

int hubDistance(int N, int sub) {
    if (sub < 3 || sub == 4) return sub1(N,sub);
    return sub3(N);
}

// int main(){
//     freopen("txt.inp","r",stdin);
//     freopen("txt.out","w",stdout);

//     int n;
//     cin >> n;
//     for (int i = 0 ; i < n ; i++)
//         for (int j = 0 ; j < n ; j++)
//             cin >> f[i][j];

//     cout << hubDistance(n,3);
//     return 0;
// }

Compilation message (stderr)

towns.cpp: In function 'int sub3(int)':
towns.cpp:164:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         for (int j = 1 ; j < dis[i].size() ; j++){
      |                          ~~^~~~~~~~~~~~~~~

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