제출 #525265

#제출 시각아이디문제언어결과실행 시간메모리
525265keta_tsimakuridzeDesignated Cities (JOI19_designated_cities)C++14
100 / 100
1625 ms60584 KiB
#include<bits/stdc++.h> #define int long long #define f first #define s second #define pii pair<int,int> #define Pii pair<int,pii> using namespace std; const int N = 2e5 + 5, mod = 1e9 + 7; // ! int t, h[N], g[N], ans[N], sz[N], n, vis[N], f[N], all[N], oneway; pii par[N]; vector<pii> x; vector<Pii> V[N]; void dfs(int u,int p,int s) { g[u] = s; x.push_back({h[u], u}); for(int i = 0; i < V[u].size(); i++) { int v = V[u][i].f; if(v== p || f[v]) continue; h[v] = h[u] + V[u][i].s.f; par[v] = {u, V[u][i].s.f}; dfs(v, u, s); } } void dfs(int u,int p) { sz[u] = 0; for(int i = 0; i < V[u].size(); i++) { int v = V[u][i].f; if(v== p || f[v]) continue; dfs(v, u); sz[u] += sz[v]; } sz[u]++; } int find(int u,int p, int Sz) { for(int i = 0; i < V[u].size(); i++) { int v = V[u][i].f; if(v== p || f[v]) continue; if(sz[v] > Sz/2) return find(v, u, Sz); } return u; } int up(int u,int c) { int dep = 0; while(!(vis[u] == c)) { dep += par[u].s; vis[u] = c; u = par[u].f; } return dep; } void decomp(int U) { dfs(U, 0); int c = find(U, 0, sz[U]); f[c] = 1; g[c] = 0; x.clear(); for(int i = 0; i < V[c].size(); i++) { int v = V[c][i].f; if(f[v]) continue; h[v] = V[c][i].s.f; dfs(v, c, v); par[v] = {h[v], c}; swap(par[v].f, par[v].s); } x.push_back({0, c}); sort(x.rbegin(), x.rend()); vector<pii> y; vis[c] = c; for(int i = 0; i < x.size(); i++) { int u = x[i].s; y.push_back({up(u, c), u}); } sort(y.rbegin(), y.rend()); int id = 0; for(int i = 0; i < y.size(); i++) { if(g[y[i].s] != g[y[0].s]) { id = i; break; } } ans[2] = max(ans[2], all[c] + y[0].f + y[id].f); int p = all[c] + y[0].f + y[id].f, cnt = 2; for(int i = 1; i < y.size(); i++) { if(i == id) continue; cnt++; p += y[i].f; ans[cnt] = max(ans[cnt], p); } // return; for(int i = 0; i < V[c].size(); i++) { if(!f[V[c][i].f]) decomp(V[c][i].f); } } void dfs1(int u,int p) { for(int i = 0; i < V[u].size(); i++) { int v = V[u][i].f; if(v == p) continue; dfs1(v, u); oneway += V[u][i].s.s; } } void dfs2(int u,int p) { all[u] = oneway; ans[1] = max(ans[1], oneway); for(int i = 0; i < V[u].size(); i++) { int v = V[u][i].f; if(v == p) continue; oneway -= V[u][i].s.s; oneway += V[u][i].s.f; dfs2(v, u); oneway -= -V[u][i].s.s; oneway += -V[u][i].s.f; } } main(){ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin >> n; int MS = 0; for(int i = 2; i <= n; i++) { int u,v,w ,a , b; cin >> u >> v >> a >> b; V[u].push_back({v, {a, b}}); V[v].push_back({u, {b, a}}); MS += a + b; } dfs1(1, 0); dfs2(1, 0); decomp(1); int q; cin >> q; while(q--) { int c; cin >> c; cout << MS - ans[c] << " "; } }

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

designated_cities.cpp: In function 'void dfs(long long int, long long int, long long int)':
designated_cities.cpp:16:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
designated_cities.cpp: In function 'void dfs(long long int, long long int)':
designated_cities.cpp:26:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
designated_cities.cpp: In function 'long long int find(long long int, long long int, long long int)':
designated_cities.cpp:35:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
designated_cities.cpp: In function 'void decomp(long long int)':
designated_cities.cpp:58:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 0; i < V[c].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
designated_cities.cpp:70:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i = 0; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~
designated_cities.cpp:76:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i = 0; i < y.size(); i++) {
      |                 ~~^~~~~~~~~~
designated_cities.cpp:84:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i = 1; i < y.size(); i++) {
      |                 ~~^~~~~~~~~~
designated_cities.cpp:91:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i = 0; i < V[c].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
designated_cities.cpp: In function 'void dfs1(long long int, long long int)':
designated_cities.cpp:96:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
designated_cities.cpp: In function 'void dfs2(long long int, long long int)':
designated_cities.cpp:106:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
designated_cities.cpp: At global scope:
designated_cities.cpp:116:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  116 | main(){
      | ^~~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:121:11: warning: unused variable 'w' [-Wunused-variable]
  121 |   int u,v,w ,a , b;
      |           ^
#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...