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;
bool operator <(const E &a)const{
return y<a.y;
}
};
vector<E> e;
vector<int> gp[MAX_N+1];
vector<E> gp2[MAX_N+1];
int p[MAX_N+1][15];
int num[MAX_N+1];
int c[MAX_N+1];
int lv[MAX_N+1];
int ans;
int dp[MAX_N+1][(1<<10)];
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){
num[gp[x][i]] = i;
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];
}
int cost(int x, int y){
int ret = 0;
int t = 0;
while(1){
ret+=dp[x][(1<<10)-1-t];
if(x==y) break;
t = (1<<num[x]);
x = p[x][0];
}
return ret;
}
void dfs2(int x){
for(int i=0; i<gp[x].size(); i++){
if(gp[x][i]!=p[x][0]){
dfs2(gp[x][i]);
}
}
for(int i=0; i<gp2[x].size(); i++){
int pp1, pp2;
E now = gp2[x][i];
pp1 = up(now.x, lv[now.x]-lv[x]-1); pp2 = up(now.y, lv[now.y]-lv[x]-1);
if(now.x==x) now.z+=cost(now.y, pp2);
else if(now.y==x) now.z+=cost(now.x, pp1);
else now.z+=cost(now.y, pp2)+cost(now.x, pp1);
for(int j=0; j<gp[x].size(); j++){
if(pp1==gp[x][j]) now.x = j;
if(pp2==gp[x][j]) now.y = j;
}
if(pp1==x) now.x = -1;
if(pp2==x) now.y = -1;
if(now.x>now.y) {int tmp = now.x; now.x = now.y; now.y = tmp;}
gp2[x][i] = now;
}
sort(gp2[x].begin(), gp2[x].end());
for(int i=0; i<(1<<10); i++) dp[x][i] = 0;
for(int i=0; i<gp[x].size(); i++){
if(gp[x][i]==p[x][0]) continue;
for(int j=0; j<(1<<10); j++){
if(((1<<i)&j)==0) continue;
dp[x][j] += dp[gp[x][i]][(1<<10)-1];
}
}
for(int i=0; i<gp2[x].size(); i++){
E now = gp2[x][i];
if(now.x==-1){
for(int j=0; j<(1<<10); j++){
if((j&(1<<now.y))!=0) continue;
dp[x][j+(1<<now.y)] = max(dp[x][j+(1<<now.y)], dp[x][j]+now.z);
}
}else{
for(int j=0; j<(1<<10); j++){
if((j&(1<<now.x))!=0) continue;
if((j&(1<<now.y))!=0) continue;
dp[x][j+(1<<now.y)+(1<<now.x)] = max(dp[x][j+(1<<now.y)+(1<<now.x)], dp[x][j]+now.z);
}
}
}
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][(1<<10)-1];
printf("%d", ans);
return 0;
}
Compilation message (stderr)
training.cpp: In function 'void dfs(int)':
training.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp[x].size(); i++){
~^~~~~~~~~~~~~
training.cpp: In function 'void dfs2(int)':
training.cpp:91:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp[x].size(); i++){
~^~~~~~~~~~~~~
training.cpp:96:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp2[x].size(); i++){
~^~~~~~~~~~~~~~
training.cpp:103:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<gp[x].size(); j++){
~^~~~~~~~~~~~~
training.cpp:114:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp[x].size(); i++){
~^~~~~~~~~~~~~
training.cpp:121:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp2[x].size(); i++){
~^~~~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:159:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<e.size(); i++){
~^~~~~~~~~
training.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
training.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | 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... |