제출 #590995

#제출 시각아이디문제언어결과실행 시간메모리
590995AlperenT도시들 (IOI15_towns)C++17
35 / 100
16 ms412 KiB
#include <bits/stdc++.h> #include "towns.h" using namespace std; const int N = 110, INF = 1e9 + 5; struct City{ int adist, bdist, acnt, bcnt; vector<int> childs; vector<pair<int, int>> childs2; }; int dist[N][N]; struct DSU{ int par[N], setsize[N]; DSU(){ for(int i = 0; i < N; i++) par[i] = i, setsize[i] = 1; } int setfind(int a){ if(par[a] == a) return par[a]; else return par[a] = setfind(par[a]); } void setunion(int a, int b){ a = setfind(a), b = setfind(b); if(a != b){ if(setsize[b] > setsize[a]) swap(a, b); par[b] = par[a]; setsize[a] += setsize[b]; } } }; DSU dsu; int hubDistance(int n, int sub){ if(sub == 3){ for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ dist[i][j] = dist[j][i] = getDistance(i, j); } } int A = max_element(dist[0], dist[0] + n) - dist[0]; int B = max_element(dist[A], dist[A] + n) - dist[A]; map<pair<int, int>, vector<pair<int, int>>> mp; for(int C = 0; C < n; C++){ int xtoc = (dist[A][C] + dist[B][C] - dist[A][B]) / 2; mp[{dist[A][C] - xtoc, dist[B][C] - xtoc}].push_back({xtoc, C}); } int mn = INF; for(auto p : mp) mn = min(mn, max(p.first.first, p.first.second)); vector<City> cities; for(auto p : mp) cities.push_back({p.first.first, p.first.second, 0, 0, {}, p.second}); int sum = 0; for(int i = 0; i < cities.size(); i++){ cities[i].acnt = sum; sum += cities[i].childs.size(); } sum = 0; for(int i = cities.size() - 1; i >= 0; i--){ cities[i].bcnt = sum; sum += cities[i].childs.size(); } vector<City> hubs; for(auto cty : cities){ if(max(cty.adist, cty.bdist) == mn && cty.acnt <= n / 2 && cty.bcnt <= n / 2){ hubs.push_back(cty); } } for(auto hub : hubs){ for(int i = 0; i < hub.childs2.size(); i++){ for(int j = i + 1; j < hub.childs2.size(); j++){ if(dist[hub.childs2[i].second][hub.childs2[j].second] != hub.childs2[i].first + hub.childs2[j].first){ dsu.setunion(hub.childs2[i].second, hub.childs2[j].second); } } } int mx = 0; for(auto p : hub.childs2) mx = max(mx, dsu.setsize[dsu.setfind(p.second)]); if(mx <= n / 2) return mn; } return -mn; } else{ int dist0[n]; for(int i = 0; i < n; i++) dist0[i] = getDistance(0, i); int A = max_element(dist0, dist0 + n) - dist0; int distA[n]; for(int i = 0; i < n; i++) distA[i] = getDistance(A, i); int B = max_element(distA, distA + n) - distA; int distB[n]; for(int i = 0; i < n; i++) distB[i] = getDistance(B, i); map<pair<int, int>, vector<int>> mp; for(int C = 0; C < n; C++){ int xtoc = (distA[C] + distB[C] - distA[B]) / 2; mp[{distA[C] - xtoc, distB[C] - xtoc}].push_back(xtoc); } int mn = INF; for(auto p : mp) mn = min(mn, max(p.first.first, p.first.second)); if(sub == 1 || sub == 2) return mn; else if(sub == 4){ vector<City> cities; for(auto p : mp) cities.push_back({p.first.first, p.first.second, 0, 0, p.second, {}}); int sum = 0; for(int i = 0; i < cities.size(); i++){ cities[i].acnt = sum; sum += cities[i].childs.size(); } sum = 0; for(int i = cities.size() - 1; i >= 0; i--){ cities[i].bcnt = sum; sum += cities[i].childs.size(); } for(auto cty : cities){ if(max(cty.adist, cty.bdist) == mn && cty.acnt <= n / 2 && cty.bcnt <= n / 2 && cty.childs.size() <= n / 2) return mn; } return -mn; } else return -1; } }

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:51:45: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   51 |   int A = max_element(dist[0], dist[0] + n) - dist[0];
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
towns.cpp:53:45: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   53 |   int B = max_element(dist[A], dist[A] + n) - dist[A];
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
towns.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<City>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for(int i = 0; i < cities.size(); i++){
      |                  ~~^~~~~~~~~~~~~~~
towns.cpp:76:33: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   76 |    sum += cities[i].childs.size();
      |                                 ^
towns.cpp:81:29: warning: conversion from 'std::vector<City>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   81 |   for(int i = cities.size() - 1; i >= 0; i--){
      |               ~~~~~~~~~~~~~~^~~
towns.cpp:84:33: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   84 |    sum += cities[i].childs.size();
      |                                 ^
towns.cpp:96:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |    for(int i = 0; i < hub.childs2.size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~
towns.cpp:97:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int j = i + 1; j < hub.childs2.size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~~~
towns.cpp:118:41: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  118 |   int A = max_element(dist0, dist0 + n) - dist0;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
towns.cpp:124:41: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  124 |   int B = max_element(distA, distA + n) - distA;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
towns.cpp:150:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<City>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |    for(int i = 0; i < cities.size(); i++){
      |                   ~~^~~~~~~~~~~~~~~
towns.cpp:153:34: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  153 |     sum += cities[i].childs.size();
      |                                  ^
towns.cpp:158:30: warning: conversion from 'std::vector<City>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  158 |    for(int i = cities.size() - 1; i >= 0; i--){
      |                ~~~~~~~~~~~~~~^~~
towns.cpp:161:34: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  161 |     sum += cities[i].childs.size();
      |                                  ^
towns.cpp:165:103: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  165 |     if(max(cty.adist, cty.bdist) == mn && cty.acnt <= n / 2 && cty.bcnt <= n / 2 && cty.childs.size() <= n / 2) return mn;
      |                                                                                     ~~~~~~~~~~~~~~~~~~^~~~~~~~
#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...