제출 #795411

#제출 시각아이디문제언어결과실행 시간메모리
795411jasmin도시들 (IOI15_towns)C++17
25 / 100
15 ms356 KiB
#include "towns.h" #include<bits/stdc++.h> using namespace std; bool balancedSlow(int n, int r, int diameter, map<int, vector<int> >& group, vector<int>& dista){ bool balanced_hub=false; int cntleft=1; for(auto [x, g]: group){ if(max(x, diameter-x)!=r){ //no hub continue; } int cntright = n-cntleft-g.size(); if(cntleft>n/2 || cntright>n/2) continue; vector<bool> vis(n, false); int open=g.size(); bool balanced=true; while(open >= n/2){ int v=g.back(); g.pop_back(); vis[v]=true; int size=1; for(auto u: g){ int d = getDistance(v, u); if(d < dista[v]-x + dista[u]-x){ //same component vis[u]=true; size++; } } if(size >= n/2) balanced = false; open -= size; } if(balanced){ balanced_hub = true; break; } cntleft += group.size(); } return balanced_hub; } int hubDistance(int n, int sub) { //find diameter vector<int> dist0(n); int a=1; for(int i=1; i<n; i++){ dist0[i] = getDistance(0, i); if(dist0[i]>dist0[a]){ a=i; } } int b=0; vector<int> dista(n); dista[0] = dist0[a]; for(int i=1; i<n; i++){ if(i==a) continue; dista[i] = getDistance(a, i); if(dista[i] > dista[b]){ b=i; } } vector<int> distb(n); distb[0] = dist0[b]; distb[a] = dista[b]; for(int i=1; i<n; i++){ if(i==a || i==b) continue; distb[i] = getDistance(b, i); } int diameter = dista[b]; //group the leafes vector<int> dleft(n); dleft[a]=0; dleft[b]=diameter; vector<int> ddiam(n); ddiam[a]=ddiam[b]=0; map<int, vector<int> > group; for(int i=0; i<n; i++){ if(i==a || i==b) continue; ddiam[i] = (dista[i]+distb[i] - diameter)/2; dleft[i] = dista[i]-ddiam[i]; group[dleft[i]].push_back(i); } //compute r int r=diameter; for(auto [x, g]: group){ r = min(r, max(x, diameter-x)); } bool balanced = false; if(2<sub){ balanced = balancedSlow(n, r, diameter, group, dista); } if(balanced){ return r; } return -r; }

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

towns.cpp: In function 'bool balancedSlow(int, int, int, std::map<int, std::vector<int> >&, std::vector<int>&)':
towns.cpp:16:33: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   16 |         int cntright = n-cntleft-g.size();
      |                        ~~~~~~~~~^~~~~~~~~
towns.cpp:20:24: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   20 |         int open=g.size();
      |                  ~~~~~~^~
towns.cpp:47:31: warning: conversion from 'std::map<int, std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   47 |         cntleft += group.size();
      |                               ^
#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...