제출 #767612

#제출 시각아이디문제언어결과실행 시간메모리
767612Cyber_Wolf도시들 (IOI15_towns)C++17
13 / 100
13 ms1108 KiB
#include "towns.h" #include <bits/stdc++.h> using namespace std; #define lg long long lg dist[200][200], r[200][200], q = 0; lg d(lg x, lg y) { if(x == y) return 0; if(~dist[x][y]) return dist[x][y]; q++; return dist[x][y] = dist[y][x] = getDistance(x, y); } int hubDistance(int N, int sub) { q = 0; for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) dist[i][j] = -1; lg s = 0; for(int i = 1; i < N; i++) { if(d(s, 0) < d(i, 0)) s = i; } lg t = 0; for(int i = 1; i < N; i++) { if(d(t, s) < d(i, s)) t = i; } map<lg, vector<lg>> mp; lg ans = 1e18; for(int i = 0; i < N; i++) { lg dis = (d(s, t)-d(t, i)+d(i, s))/2; ans = min(ans, max(d(s, t)-dis, dis)); mp[dis].push_back(i); } lg left = 0; for(auto [val, a] : mp) { if(left > N/2 || N-left-a.size() > N/2) continue; if(ans == max(val, d(s, t)-val)) { vector<vector<lg>> dead, alive; for(auto it : a) alive.push_back({it}); vector<lg> last; while(alive.size()) { vector<vector<lg>> new_v; for(int i = 0; i < alive.size(); i += 2) { if(i+1 == alive.size()) { if(last.size()) dead.push_back(last); last = alive[i]; continue; } if(d(s, alive[i][0])+d(s, alive[i+1][0])-d(alive[i][0], alive[i+1][0]) > 2*val) { for(auto it : alive[i+1]) alive[i].push_back(it); new_v.push_back(alive[i]); } else{ dead.push_back(alive[i]); dead.push_back(alive[i+1]); } } swap(alive, new_v); } if(last.empty()) return ans; lg cnt = last.size(); for(auto it : dead) { if(d(s, it[0])+d(s, last[0])-d(last[0], it[0]) > 2*val) cnt += it.size(); } if(cnt <= N/2) return ans; } left += a.size(); } return -ans; }

컴파일 시 표준 에러 (stderr) 메시지

towns.cpp: In function 'long long int d(long long int, long long int)':
towns.cpp:16:47: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 |  return dist[x][y] = dist[y][x] = getDistance(x, y);
      |                                               ^
towns.cpp:16:50: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 |  return dist[x][y] = dist[y][x] = getDistance(x, y);
      |                                                  ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:44:39: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   44 |      if(left > N/2 || N-left-a.size() > N/2) continue;
      |                       ~~~~~~~~~~~~~~~~^~~~~
towns.cpp:53:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |        for(int i = 0; i < alive.size(); i += 2)
      |                       ~~^~~~~~~~~~~~~~
towns.cpp:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         if(i+1 == alive.size())
      |            ~~~~^~~~~~~~~~~~~~~
towns.cpp:73:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   73 |       if(last.empty()) return ans;
      |                               ^~~
towns.cpp:79:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |       if(cnt <= N/2) return ans;
      |                             ^~~
towns.cpp:83:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |  return -ans;
      |         ^~~~
towns.cpp:19:28: warning: unused parameter 'sub' [-Wunused-parameter]
   19 | int hubDistance(int N, int sub)
      |                        ~~~~^~~
#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...