제출 #990738

#제출 시각아이디문제언어결과실행 시간메모리
990738starchan도시들 (IOI15_towns)C++17
컴파일 에러
0 ms0 KiB
#include<bits/stdc++.h> #include "towns.h" using namespace std; #define in array<int, 2> #define pb push_back #define pob pop_back int getDistance(int x, int u){return x+u;} int hubDistance(int n, int sub) { in opt = {0, 0}; for(int i = 1; i < n; i++) opt = max(opt, {getDistance(i, 0), i}); int a = opt[1]; opt = {0, a}; vector<int> d1(n), d2(n); d1[a] = 0; for(int i = 0; i < n; i++) { if(i == a) continue; opt = max(opt, {d1[i] = getDistance(i, a), i}); } auto [D, b] = opt; d2[b] = 0; map<int, vector<int>> diam; diam[0].pb(a); diam[D].pb(b); for(int i = 0; i < n; i++) { if(i == a || i == b) continue; d2[i] = getDistance(i, b); diam[(d1[i]-d2[i]+D)/2].pb(i); } int R = 1e9+1; vector<vector<int>> vi; vector<int> dist; for(auto [X, v]: diam) { R = min(R, max(X, D-X)); vi.pb(v); dist.pb(X); } int N = vi.size(); //0, 1, .., N-1 //has information for stuff on diameter. int pre = 0; for(int i = 0; i < N-2; i++) { pre+=vi[i].size(); if(R != max(dist[i+1], D-dist[i+1])) continue; if(2*pre > n) break; if(2*((int)n-pre-vi[i+1].size()) > n) continue; if(2*((int)vi[i+1].size()) <= n) return R; //Now we need to check if the i+1th thingie, (as we are accessing) is centroid or not. //This must be done in <= N/2 queries for AC. <= 2N queries is ok too, if we want good partial score. int g = vi[i+1][0]; int rt = d1[g]-dist[i+1]; int cnt = 0; for(auto x: vi[i+1]) { if(x == g) continue; int q_rt = d1[x]-dist[i+1]; if((rt+q_rt) == getDistance(x, g)) { if(cnt) cnt--; else { cnt = 1; rt = q_rt; g = x; } } else cnt++; } int SP = 1; for(auto x: vi[i+1]) { if(x == g) continue; int q_rt = d1[x]-dist[i+1]; if((rt+q_rt) == getDistance(x, g)) SP++; } if((2*SP) <= n) return R; } return -R; }

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:39:17: warning: conversion from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   39 |  int N = vi.size();
      |          ~~~~~~~^~
towns.cpp:45:19: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   45 |   pre+=vi[i].size();
      |                   ^
towns.cpp:50:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |   if(2*((int)n-pre-vi[i+1].size()) > n)
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
towns.cpp:10:28: warning: unused parameter 'sub' [-Wunused-parameter]
   10 | int hubDistance(int n, int sub)
      |                        ~~~~^~~
/usr/bin/ld: /tmp/cc5e89r9.o: in function `getDistance(int, int)':
grader.c:(.text+0x110): multiple definition of `getDistance(int, int)'; /tmp/ccrA7NBa.o:towns.cpp:(.text+0x2c0): first defined here
collect2: error: ld returned 1 exit status