이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |