Submission #1066384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066384		anango	Towns (IOI15_towns)	C++17	0 / 100	10 ms	860 KiB

towns

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

int INF = 1LL<<60;
int n;

map<pair<int,int>,int> cache;

int getdist(int u, int v) {
    if (u==v) {
        return 0;
    }
    if (u>v) swap(u,v);
    if (cache.count({u,v})) {
        return cache[{u,v}];
    }
    int g = getDistance(u,v);
    //cout << "DISTANCE " << u <<" " << v <<" " << g << endl;
    return cache[{u,v}] = g;
}

signed hubDistance(signed N, signed sub) {
    cache.clear();
    if (sub<=6) {
        n=N;
        
        vector<int> dist0(n);
        for (int i=0; i<n; i++) {
            dist0[i] = getdist(0,i);
        }
        vector<int> cities(n); iota(cities.begin(), cities.end(), (int)0);
        vector<int> sortedbyd0(cities.begin(), cities.end());
        sort(sortedbyd0.begin(), sortedbyd0.end(), [&](const int i1, const int i2) {
            return dist0[i1]<dist0[i2];
        });
        int u = sortedbyd0.back();
        vector<int> distu(n);
        for (int i=0; i<n; i++) {
            distu[i] = getdist(u,i);
        }
        
        //2n-3 used
        vector<int> sortedbydu(cities.begin(), cities.end());
        sort(sortedbydu.begin(), sortedbydu.end(), [&](const int i1, const int i2) {
            return distu[i1]<distu[i2];
        });
        int v = sortedbydu.back();
        //u-v is a diameter
        int length = distu[v];
        vector<int> disttodiamentrypointfrom0(n,-1);
        for (int i=0; i<n; i++) {
            int tautau = dist0[i]+dist0[u]-distu[i]; assert(tautau%2==0);
            disttodiamentrypointfrom0[i] = (tautau)/2;
        }
        vector<int> diameter_nodes;
        for (int i=0; i<n; i++) {
            if (disttodiamentrypointfrom0[i]==dist0[i]) {
                diameter_nodes.push_back(i);
            }
        }
        //must compute R
        //we know distance from u to v, and we know distance from 0 to u
        //we need distance from 0 to LCA of those paths
        //which is equal to dist(0,u)+dist(0,v)-dist(u,v)
        //thusfore, R is that max(dist(0,v),dist(0,u)) - LCA
        int R = max(dist0[u],dist0[v])-disttodiamentrypointfrom0[v];
        //cout << u <<" " << v << endl;
        for (int i=0; i<n; i++) {
            //cout << i <<" " << dist0[i] <<" " << disttodiamentrypointfrom0[i] << endl;
        }
        //actually the entrypoint on the path [0,u]
        map<int,vector<int>> cities2;
        for (int i=0; i<n; i++) {
            cities2[disttodiamentrypointfrom0[i]].push_back(i);
        }
        int befsum = 0;
        vector<pair<int,int>> possible_hubs; //index, 
        for (auto diameter_entrypoint:cities2) {
            int dis = diameter_entrypoint.first;
            vector<int> cits = diameter_entrypoint.second;
            int k = cits.size();
            befsum+=cits.size();
        }
        

        return R;
    }
    else {
        return 0;
    }

}

Compilation message (stderr)

towns.cpp: In function 'long long int getdist(long long int, long long int)':
towns.cpp:19:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   19 |     int g = getDistance(u,v);
      |                         ^
towns.cpp:19:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   19 |     int g = getDistance(u,v);
      |                           ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:81:17: warning: unused variable 'dis' [-Wunused-variable]
   81 |             int dis = diameter_entrypoint.first;
      |                 ^~~
towns.cpp:83:17: warning: unused variable 'k' [-Wunused-variable]
   83 |             int k = cits.size();
      |                 ^
towns.cpp:88:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   88 |         return R;
      |                ^
towns.cpp:51:13: warning: unused variable 'length' [-Wunused-variable]
   51 |         int length = distu[v];
      |             ^~~~~~

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