Submission #586727

#TimeUsernameProblemLanguageResultExecution timeMemory
586727InternetPerson10Towns (IOI15_towns)C++17
25 / 100
24 ms368 KiB
#include "towns.h" #include <bits/stdc++.h> typedef long long ll; using namespace std; map<pair<int, int>, int> distances; int getDist(int i, int j) { if(i == j) return 0; if(i > j) swap(i, j); if(distances.count({i, j})) { return distances[make_pair(i, j)]; } return distances[make_pair(i, j)] = getDistance(i, j); } vector<int> dists; map<ll, int> xs; int hubDistance(int n, int sub) { ll ans = 2e10; distances.clear(); dists.clear(); xs.clear(); dists.resize(n); int ma = -1, best = -1; for(int i = 0; i < n; i++) { dists[i] = getDist(0, i); if(ma < dists[i]) { ma = dists[i]; best = i; } } int x = best; ma = -1, best = -1; for(int i = 0; i < n; i++) { dists[i] = getDist(x, i); if(ma < dists[i]) { ma = dists[i]; best = i; } } int y = best; ll c = ma; for(int i = 0; i < n; i++) { if(i == x || i == y) continue; int a = getDist(x, i); int b = getDist(y, i); ans = min(ans, max(a + c - b, b + c - a)); if(!xs.count(a+c-b)) { xs[a+c-b] = 1; } else xs[a+c-b]++; } int cand = -1; int sum = 0; for(auto p : xs) { bool ok = true; ok &= (sum <= n/2); sum += p.second; if(sub == 4) ok &= (p.second <= n/2); ok &= (sum >= n - n/2); if(ok) cand = p.first; } if(sub == 4) { if(cand == -1) return -ans; return ans; } return ans/2; }

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:64:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   64 |         if(ok) cand = p.first;
      |                       ~~^~~~~
towns.cpp:67:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   67 |         if(cand == -1) return -ans;
      |                               ^~~~
towns.cpp:68:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   68 |         return ans;
      |                ^~~
towns.cpp:70:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   70 |     return ans/2;
      |            ~~~^~
#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...