Submission #434037

#TimeUsernameProblemLanguageResultExecution timeMemory
434037benedict0724도시들 (IOI15_towns)C++17
25 / 100
27 ms348 KiB
#include "towns.h" #include <bits/stdc++.h> using namespace std; int S = 0, E; const int INF = 1e9; int dist[110], dist2[110], distD[110], Hub[110], tmp[110], x[110], y[110]; vector<pair<int, int>> v; bool getSame(int x, int y) { if(Hub[x] + Hub[y] > getDistance(x, y)) return true; return false; } int hubDistance(int N, int sub) { v.clear(); for(int i=0;i<N;i++) dist[i] = dist2[i] = Hub[i] = x[i] = y[i] = 0; for(int i=1;i<N;i++) dist[i] = getDistance(S, i); E = 1; for(int i=1;i<N;i++) if(dist[E] < dist[i]) E = i; for(int i=0;i<N;i++) { if(i == E) continue; dist2[i] = getDistance(i, E); } int Rad = dist[E]; int opt = INF; for(int i=1;i<N;i++) { if(i == E) continue; distD[i] = (dist[i] + dist2[i] - Rad)/2; x[i] = (dist[i] + Rad - dist2[i])/2; y[i] = (-dist[i] + Rad + dist2[i])/2; } for(int i=1;i<N;i++) { if(i == E) continue; int M = max(x[i], Rad - x[i]); for(int j=1;j<N;j++) { if(j == E) continue; tmp[j] = distD[j] + abs(x[i] - x[j]); M = max(M, tmp[j]); } if(M < opt) { opt = M; Hub[S] = x[i]; Hub[E] = Rad - x[i]; for(int j=1;j<N;j++) { if(j == E) continue; Hub[j] = tmp[j]; } } } int R = 0; for(int i=0;i<N;i++) R = max(R, Hub[i]); stack<int> st; st.push(0); for(int i=1,j=0;i<N;i++) { if(st.empty()) { st.push(i); continue; } int t = st.top(); if(getSame(t, i)) st.push(i); else { st.pop(); v.push_back({i, 1}); if(st.empty()) { v.push_back({t, (i-j+1)/2}); j = i+1; } } } if(st.empty()) return R; int t = st.top(); int cnt = st.size(); for(auto i : v) { if(getSame(i.first, t)) cnt += i.second; } if(cnt > N/2) return -R; return R; }

Compilation message (stderr)

towns.cpp: In function 'bool getSame(int, int)':
towns.cpp:11:25: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   11 | bool getSame(int x, int y)
      |                     ~~~~^
towns.cpp:8:68: note: shadowed declaration is here
    8 | int dist[110], dist2[110], distD[110], Hub[110], tmp[110], x[110], y[110];
      |                                                                    ^
towns.cpp:11:18: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   11 | bool getSame(int x, int y)
      |              ~~~~^
towns.cpp:8:60: note: shadowed declaration is here
    8 | int dist[110], dist2[110], distD[110], Hub[110], tmp[110], x[110], y[110];
      |                                                            ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:88:22: warning: conversion from 'std::stack<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   88 |     int cnt = st.size();
      |               ~~~~~~~^~
towns.cpp:17:28: warning: unused parameter 'sub' [-Wunused-parameter]
   17 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~
#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...