제출 #827877

#제출 시각아이디문제언어결과실행 시간메모리
827877I_Love_EliskaM_도시들 (IOI15_towns)C++17
61 / 100
14 ms860 KiB
#include "towns.h" #include <bits/stdc++.h> using namespace std; #define forn(i,n) for(int i=0;i<n;++i) #define pb push_back #define all(x) x.begin(), x.end() #define pi pair<int,int> #define f first #define s second const int inf=1e9+9; int p1(int n) { vector<int> a(n), b(n), c(n); int f=0; forn(i,n) { a[i]=getDistance(0,i); if (a[i]>a[f]) f=i; } int s=0; forn(i,n) { b[i]=getDistance(f,i); if (b[i]>b[s]) s=i; } forn(i,n) { c[i]=getDistance(s,i); } set<int> st; vector<int> d(n); map<int,vector<int>> ok; forn(i,n) { if (i==f || i==s) continue; int x=b[i], y=c[i], z=b[s]; int A=(x-y+z)/2; d[i]=x-A; st.insert(A); ok[A].pb(i); } int ans=inf; for(auto&x:st) { int y=b[s]-x; ans=min(ans,max(x,y)); } int l=1; for(auto&x:st) { int y=b[s]-x; if (max(x,y)!=ans) { l+=ok[x].size(); continue; } int r=n-ok[x].size()-l; if (max(l,r)>n/2) continue; int t=ok[x].size(); if (t<=n/2) return ans; } return -ans; } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int p5(int n) { vector<int> a(n), b(n), c(n); int f=0; forn(i,n) { a[i]=getDistance(0,i); if (a[i]>a[f]) f=i; } int s=0; forn(i,n) { b[i]=getDistance(f,i); if (b[i]>b[s]) s=i; } forn(i,n) { c[i]=getDistance(s,i); } set<int> st; vector<int> d(n); map<int,vector<int>> ok; forn(i,n) { if (i==f || i==s) continue; int x=b[i], y=c[i], z=b[s]; int A=(x-y+z)/2; d[i]=x-A; st.insert(A); ok[A].pb(i); } int ans=inf; for(auto&x:st) { int y=b[s]-x; ans=min(ans,max(x,y)); } int l=1; int last=-1; for(auto&x:st) { l+=ok[last].size(); last=x; int y=b[s]-x; if (max(x,y)!=ans) continue; int r=n-ok[x].size()-l; if (max(l,r)>n/2) continue; int t=ok[x].size(); if (t<=n/2) return ans; vector<pi> a,b; for(auto&v:ok[x]) a.pb({v,1}); while (a.size()>1) { int k = a.size(); for (int i=0; i+1<a.size(); i+=2) { int z = getDistance(a[i].f,a[i+1].f); int x = d[a[i].f], y = d[a[i+1].f]; if (z==x+y) { if (a[i].s > a[i+1].s) b.pb(a[i]); else b.pb(a[i+1]); continue; } b.pb({a[i].f,a[i].s+a[i+1].s}); } if (k&1) b.pb(a.back()); a=b; b.clear(); } int u=a[0].f; int sz=0; for(auto&v:ok[x]) { int z = getDistance(u,v); int x = d[u], y = d[v]; if (z<x+y) ++sz; } if (sz<=n/2) return ans; } return -ans; } int hubDistance(int n, int sub) { if (sub<=2 || sub==4) return p1(n); if (sub>=3) return p5(n); return 0; }

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

towns.cpp: In function 'int p1(int)':
towns.cpp:51:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   51 |       l+=ok[x].size();
      |                     ^
towns.cpp:54:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   54 |     int r=n-ok[x].size()-l;
      |           ~~~~~~~~~~~~~~^~
towns.cpp:56:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   56 |     int t=ok[x].size();
      |           ~~~~~~~~~~^~
towns.cpp: In function 'int p5(int)':
towns.cpp:102:22: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  102 |     l+=ok[last].size(); last=x;
      |                      ^
towns.cpp:105:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  105 |     int r=n-ok[x].size()-l;
      |           ~~~~~~~~~~~~~~^~
towns.cpp:107:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  107 |     int t=ok[x].size();
      |           ~~~~~~~~~~^~
towns.cpp:109:16: warning: declaration of 'a' shadows a previous local [-Wshadow]
  109 |     vector<pi> a,b;
      |                ^
towns.cpp:65:15: note: shadowed declaration is here
   65 |   vector<int> a(n), b(n), c(n);
      |               ^
towns.cpp:109:18: warning: declaration of 'b' shadows a previous local [-Wshadow]
  109 |     vector<pi> a,b;
      |                  ^
towns.cpp:65:21: note: shadowed declaration is here
   65 |   vector<int> a(n), b(n), c(n);
      |                     ^
towns.cpp:112:21: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  112 |       int k = a.size();
      |               ~~~~~~^~
towns.cpp:113:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |       for (int i=0; i+1<a.size(); i+=2) {
      |                     ~~~^~~~~~~~~
towns.cpp:115:13: warning: declaration of 'x' shadows a previous local [-Wshadow]
  115 |         int x = d[a[i].f], y = d[a[i+1].f];
      |             ^
towns.cpp:101:12: note: shadowed declaration is here
  101 |   for(auto&x:st) {
      |            ^
towns.cpp:115:28: warning: declaration of 'y' shadows a previous local [-Wshadow]
  115 |         int x = d[a[i].f], y = d[a[i+1].f];
      |                            ^
towns.cpp:103:9: note: shadowed declaration is here
  103 |     int y=b[s]-x;
      |         ^
towns.cpp:131:11: warning: declaration of 'x' shadows a previous local [-Wshadow]
  131 |       int x = d[u], y = d[v];
      |           ^
towns.cpp:101:12: note: shadowed declaration is here
  101 |   for(auto&x:st) {
      |            ^
towns.cpp:131:21: warning: declaration of 'y' shadows a previous local [-Wshadow]
  131 |       int x = d[u], y = d[v];
      |                     ^
towns.cpp:103:9: note: shadowed declaration is here
  103 |     int y=b[s]-x;
      |         ^
#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...