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 <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
vector<vector<int>> paved;
vector<vector<int>> child;
vector<pair<pair<int,int>, int>> edges;
map<int, int> memo;
int dp(int x){
if(memo.find(x)!=memo.end()) return memo[x];
if(x==n) return memo[x]=0;
int mx=dp(x+1);
for (int i = 0; i < m-(n-1); i++)
{
if(edges[i].first.first==x){
int b=edges[i].first.second;
int c=edges[i].second;
if((b-x)%2!=0) continue;
mx=max(dp(b)+c,mx);
}
}
return memo[x]=mx;
}
signed main() {
// Input:
ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>n>>m;
vector<int> conv(n+1);
paved.resize(n+1);
child.resize(n+1);
int sum=0;
for (int i = 0; i < m; i++)
{
int a,b,c; cin >> a >> b >> c;
sum+=c;
if(a>b) swap(a,b);
if(c==0) {
paved[a].push_back(b);
paved[b].push_back(a);
}
else edges.push_back({{a,b},c});
}
int c=-1;
for (int i = n; i >= 1; i--) { if(paved[i].size()==1) c=i; }
int p=-1;
int i=1;
while(i<=n){
conv[c]=i;
if(paved[c][0]==p){
p=c;
c=paved[c][1];
}
else {
p=c;
c=paved[c][0];
}
i++;
}
for (int j = 0; j < m-(n-1); j++)
{
edges[j].first.first=conv[edges[j].first.first];
edges[j].first.second=conv[edges[j].first.second];
if(edges[j].first.first>edges[j].first.second) swap(edges[j].first.first,edges[j].first.second);
}
vector<bool> cyc(n+1);
cout << sum-dp(0) << "\n";
return 0;
}
# | 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... |