제출 #761814

#제출 시각아이디문제언어결과실행 시간메모리
761814Red_Inside도시들 (IOI15_towns)C++17
0 / 100
21 ms24660 KiB
#include "towns.h" #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdio.h> #include <stdlib.h> #include <sys/types.h> #include <unistd.h> #include <bits/stdc++.h> #include <time.h> //#pragma GCC optimize("Ofast") //#pragma GCC target("avx,avx2,fma") //#pragma GCC optimization ("unroll-loops") #define ll long long #define f first #define s second #define pb push_back #define mp make_pair #define o cout<<"BUG"<<endl; #define FOR(i, j, n) for(int j = i; j < n; ++j) #define forn(i, j, n) for(int j = i; j <= n; ++j) #define nfor(i, j, n) for(int j = n; j >= i; --j) #define all(v) v.begin(), v.end() #define ld long double #define ull unsigned long long using namespace std; const int maxn=1e6+10,LOG=17,mod=1e9+7; int block = 340, timer = 0; const double eps = 1e-9; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define bt(i) (1 << (i)) //#define int ll const int inf=2e9+10; #define y1 yy #define prev pre #define pii pair <int, int> int n, have, dist[500][500], cnt; vector <pair <pii, int> > edges; vector <pii> edge[maxn]; int getdist(int v, int u) { if(v == u) return 0; if(dist[v][u] != -1) return dist[v][u]; dist[v][u] = getDistance(v, u); dist[u][v] = dist[v][u]; return dist[v][u]; } void solve(int pred, int V, vector <pii> ver) { // cout << "SOLVE " << pred << " " << V << endl; // for(auto i : ver) cout << i.f << " "; // cout << endl; int fi = ver.back().f; int d1 = ver.back().s; ver.pop_back(); vector <pii> first, second; first.pb({fi, d1}); int mn = inf; while(ver.size()) { int v = ver.back().f; int d2 = ver.back().s; ver.pop_back(); if((d1+d2-getdist(fi, v)) / 2 < mn) { // cout << " " << v << " " << d2 << " " << (d1+d2-getdist(fi, v))/2 << endl; mn = (d1+d2-getdist(fi, v)) / 2; while(second.size()) { first.pb(second.back()); second.pop_back(); } second.pb({v, d2}); } else if((d1+d2-getdist(fi, v)) / 2 == mn) { second.pb({v, d2}); } else { first.pb({v, d2}); } } FOR(0, i, first.size()) { first[i].s -= mn; } FOR(0, i, second.size()) { second[i].s -= mn; } edges.pb({{pred, V}, mn}); if(first.size() == 1) edges.pb({{first[0].f, V}, first[0].s}); else solve(V, ++cnt, first); if(second.size() == 1) edges.pb({{second[0].f, V}, second[0].s}); else solve(V, ++cnt, second); } int sz[maxn], deep[maxn]; ll mxdist[maxn]; void dfs(int v, int pred) { if(edge[v].size() == 1) sz[v] = 1; mxdist[v] = 0; for(auto to : edge[v]) { if(to.f == pred) continue; deep[to.f] = deep[v] + to.s; dfs(to.f, v); mxdist[v] = max(mxdist[v], mxdist[to.f] + to.s); sz[v] += sz[to.f]; } int ok = 1; for(auto to : edge[v]) { if(to.f == pred) { if(n - sz[v] > n / 2) ok = 0; } else { if(sz[to.f] > n / 2) ok = 0; } } if(ok) have = 1; } ll dpup[maxn]; void dfs2(int v, int pred = -1) { vector <ll> pref(edge[v].size()), suff(edge[v].size()); pref[0] = (edge[v][0].f == pred ? 0 : mxdist[edge[v][0].f] + edge[v][0].s); FOR(1, i, edge[v].size()) { pref[i] = pref[i - 1]; if(edge[v][i].f == pred) continue; pref[i] = max(pref[i], mxdist[edge[v][i].f] + edge[v][i].s); } suff[(int)edge[v].size() - 1] = (edge[v].back().f == pred ? 0 : mxdist[edge[v].back().f] + edge[v].back().s); for(int i = (int)edge[v].size() - 2; i >= 0; --i) { suff[i] = suff[i + 1]; if(edge[v][i].f == pred) continue; suff[i] = max(suff[i], mxdist[edge[v][i].f] + edge[v][i].s); } FOR(0, i, edge[v].size()) { pii to = edge[v][i]; if(to.f == pred) continue; dpup[to.f] = to.s+max({dpup[v], (i>0?pref[i-1]:0), (i+1<(int)edge[v].size()?suff[i+1]:0)}); dfs2(to.f, v); } } int hubDistance(int n, int sub) { have = 0; forn(0, i, n-1) { forn(0, j, n-1) { dist[i][j] = -1; } } edges.clear(); cnt = n-1; vector <pii> vec; forn(1, i, n-1) { vec.pb({i, getdist(0, i)}); } solve(0, ++cnt, vec); forn(0, i, cnt) edge[i].clear(); for(auto i : edges) { edge[i.f.f].pb({i.f.s, i.s}); edge[i.f.s].pb({i.f.f, i.s}); } deep[0] = 0; dfs(0, -1); dfs2(0); int res = 0; forn(n, i, cnt) { if(max(dpup[i], mxdist[i]) > res) res = max(dpup[i], mxdist[i]); } return res * (have ? 1 : -1); } /* 1 1 4 0 35 44 31 35 0 29 16 44 29 0 21 31 16 21 0 */

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

towns.cpp: In function 'void solve(int, int, std::vector<std::pair<int, int> >)':
towns.cpp:22:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
   93 |  FOR(0, i, first.size())
      |         ~~~~~~~~~~~~~~~                
towns.cpp:93:2: note: in expansion of macro 'FOR'
   93 |  FOR(0, i, first.size())
      |  ^~~
towns.cpp:22:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
   97 |  FOR(0, i, second.size())
      |         ~~~~~~~~~~~~~~~~               
towns.cpp:97:2: note: in expansion of macro 'FOR'
   97 |  FOR(0, i, second.size())
      |  ^~~
towns.cpp: In function 'void dfs2(int, int)':
towns.cpp:22:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
  149 |  FOR(1, i, edge[v].size())
      |         ~~~~~~~~~~~~~~~~~              
towns.cpp:149:2: note: in expansion of macro 'FOR'
  149 |  FOR(1, i, edge[v].size())
      |  ^~~
towns.cpp:22:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
  162 |  FOR(0, i, edge[v].size())
      |         ~~~~~~~~~~~~~~~~~              
towns.cpp:162:2: note: in expansion of macro 'FOR'
  162 |  FOR(0, i, edge[v].size())
      |  ^~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:172:21: warning: declaration of 'n' shadows a global declaration [-Wshadow]
  172 | int hubDistance(int n, int sub)
      |                 ~~~~^
towns.cpp:43:5: note: shadowed declaration is here
   43 | int n, have, dist[500][500], cnt;
      |     ^
towns.cpp:202:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  202 |   if(max(dpup[i], mxdist[i]) > res) res = max(dpup[i], mxdist[i]);
      |                                           ~~~^~~~~~~~~~~~~~~~~~~~
towns.cpp:172:28: warning: unused parameter 'sub' [-Wunused-parameter]
  172 | 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...