제출 #133758

#제출 시각아이디문제언어결과실행 시간메모리
133758Mahdi_Jfri도시들 (IOI15_towns)C++14
35 / 100
21 ms1204 KiB
#include "towns.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int maxn = 1e2 + 20; int h[2][maxn] , d[maxn] , p[maxn]; vector<int> ver[maxn]; bool cmp(int x , int y) { return d[x] > d[y]; } int root(int v) { return p[v] < 0? v : p[v] = root(p[v]); } void merge(int a , int b) { a = root(a) , b = root(b); if(a == b) return; p[a] += p[b]; p[b] = a; } int hubDistance(int n, int sub) { memset(h , 0 , sizeof h); for(int i = 1; i < n; i++) h[0][i] = getDistance(0 , i); int a = max_element(h[0] , h[0] + n) - h[0]; memset(h[0] , 0 , sizeof h[0]); for(int i = 0; i < n; i++) if(i != a) h[0][i] = getDistance(a , i); int b = max_element(h[0] , h[0] + n) - h[0]; for(int i = 0; i < n; i++) if(i != b) h[1][i] = getDistance(b , i); vector<int> val; int ans = 1e9; for(int i = 0; i < n; i++) { int k = (h[0][i] - h[1][i] + h[0][b]) / 2; val.pb(k); d[i] = h[0][i] - k; while(h[1][i] - d[i] != h[0][b] - k); ans = min(ans , max(k , h[0][b] - k)); } sort(val.begin() , val.end()); val.resize(unique(val.begin() , val.end()) - val.begin()); int m = val.size(); for(int i = 0; i < m; i++) ver[i].clear(); for(int i = 0; i < n; i++) { int k = (h[0][i] - h[1][i] + h[0][b]) / 2; k = lower_bound(val.begin() , val.end() , k) - val.begin(); ver[k].pb(i); } if(sub <= 2) return ans; for(int i = 0; i < m; i++) if(max(val[i] , h[0][b] - val[i]) == ans) { int k = ver[i].size() , s1 = 0 , s2 = 0; for(int j = 0; j < i; j++) s1 += ver[j].size(); s2 = n - k - s1; if(max(s1 , s2) > n / 2) continue; if(k <= n / 2) return ans; continue; } for(int i = 0; i < m; i++) if(max(val[i] , h[0][b] - val[i]) == ans) { int k = ver[i].size() , s1 = 0 , s2 = 0; for(int j = 0; j < i; j++) s1 += ver[j].size(); s2 = n - k - s1; if(max(s1 , s2) > n / 2 || k <= n) continue; memset(p , -1 , sizeof p); sort(ver[i].begin() , ver[i].end() , cmp); int rem = k; bool f = 1; for(int j = 0; j < k && rem > n / 2; j++) { int v = ver[i][j]; if(p[v] >= 0) continue; for(int l = j + 1; l < k && -p[v] <= n / 2; l++) { int u = ver[i][l]; if(p[u] < 0 && getDistance(v , u) != d[v] + d[u]) { p[v] += p[u]; p[u] = v; } } if(-p[v] > n / 2) { f = 0; break; } rem -= -p[v]; } for(auto v : ver[i]) if(-p[v] > n / 2) f = 0; if(f) return ans; } return -ans; }

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:41:39: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  int a = max_element(h[0] , h[0] + n) - h[0];
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:48:39: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  int b = max_element(h[0] , h[0] + n) - h[0];
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:67:18: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int m = val.size();
          ~~~~~~~~^~
towns.cpp:74:48: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   k = lower_bound(val.begin() , val.end() , k) - val.begin();
       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
towns.cpp:84:23: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
    int k = ver[i].size() , s1 = 0 , s2 = 0;
            ~~~~~~~~~~~^~
towns.cpp:86:23: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     s1 += ver[j].size();
                       ^
towns.cpp:100:23: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
    int k = ver[i].size() , s1 = 0 , s2 = 0;
            ~~~~~~~~~~~^~
towns.cpp:102:23: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     s1 += ver[j].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...