# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
94921 | Retro3014 | Training (IOI07_training) | C++17 | 4 ms | 632 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#define MAX_N 1000
using namespace std;
int N, M;
struct S{
int idx, data;
};
struct E{
int x, y, z;
};
vector<E> e;
vector<int> gp[MAX_N+1];
vector<E> gp2[MAX_N+1];
int p[MAX_N+1][15];
int c[MAX_N+1];
int lv[MAX_N+1];
int ans;
int dp[MAX_N+1];
void dfs(int x){
for(int i=1; i<15; i++){
p[x][i] = p[p[x][i-1]][i-1];
}
for(int i=0; i<gp[x].size(); i++){
if(c[gp[x][i]]==0){
c[gp[x][i]] = 3 - c[x];
p[gp[x][i]][0] = x;
lv[gp[x][i]] = lv[x] + 1;
dfs(gp[x][i]);
}
}
}
int up(int x, int y){
int two = (1<<14);
for(int i=14; i>=0; i--){
if(y>=two){
x = p[x][i];
y-=two;
}
two/=2;
}
return x;
}
int lca(int x, int y){
if(lv[x]>lv[y]){
x = up(x, lv[x]-lv[y]);
}
if(lv[x]<lv[y]){
y = up(y, lv[y]-lv[x]);
}
if(x==y) return x;
for(int i=14; i>=0; i--){
if(p[x][i]!=p[y][i]){
x = p[x][i]; y = p[y][i];
}
}
if(x==y) return x;
return p[x][0];
}
void dfs2(int x){
dp[x] = 0;
for(int i=0; i<gp[x].size(); i++){
if(gp[x][i]!=p[x][0]){
dfs2(gp[x][i]);
dp[x]+=dp[gp[x][i]];
}
}
for(int i=0; i<gp2[x].size(); i++){
int k = 0, pp1, pp2;
E now = gp2[x][i];
if(now.y==x){int tmp = now.x; now.x = now.y; now.y = tmp;}
if(now.x==x){
pp1 = up(now.y, lv[now.y]-lv[x]-1);
k = now.z + dp[now.y];
for(int j=0; j<gp[x].size(); j++){
if(gp[x][j]!=p[x][0] && gp[x][j]!=pp1){
k+=dp[gp[x][j]];
}
}
}else{
pp1 = up(now.x, lv[now.x]-lv[x]-1); pp2 = up(now.y, lv[now.y]-lv[x]-1);
k = now.z + dp[now.x] + dp[now.y];
for(int j=0; j<gp[x].size(); j++){
if(gp[x][j]!=p[x][0] && gp[x][j]!=pp1 && gp[x][j]!=pp2){
k+=dp[gp[x][j]];
}
}
}
dp[x] = max(dp[x], k);
}
return;
}
int degree[MAX_N+1];
int main(){
scanf("%d%d", &N, &M);
for(int i=0; i<M; i++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if(c==0){
degree[a]++; degree[b]++;
gp[a].push_back(b); gp[b].push_back(a);
}else{
e.push_back({a, b, c});
ans+=c;
}
}
int now=1;
c[now] = 1;
lv[now] = 1;
dfs(now);
for(int i=0; i<e.size(); i++){
if(c[e[i].x]==c[e[i].y]){
gp2[lca(e[i].x, e[i].y)].push_back(e[i]);
}
}
dfs2(now);
ans-=dp[now];
printf("%d", ans);
return 0;
}
Compilation message (stderr)
# | 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... |
# | 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... |