Submission #895713

#TimeUsernameProblemLanguageResultExecution timeMemory
895713LudisseyTraining (IOI07_training)C++14
10 / 100
1067 ms1464 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int n,m; vector<vector<int>> paved; vector<pair<pair<int,int>, int>> edges; map<pair<vector<bool>, int>, int> memo; int dp(vector<bool> cyc, int x){ if(memo.find({cyc, x})!=memo.end()) return memo[{cyc,x}]; if(x==m-(n-1)) return memo[{cyc,x}]=0; int mx=0; for (int e = x; e < m-(n-1); e++) { int a=edges[e].first.first,b=edges[e].first.second,c=edges[e].second; if(abs(a-b)%2!=0) continue; bool br=false; for (int i = min(a,b); i < max(a,b); i++) { if(cyc[i]) { br=true; break; } } if(br) continue; for (int i = min(a,b); i < max(a,b); i++) cyc[i]=true; mx=max(dp(cyc, e+1)+c,mx); for (int i = min(a,b); i < max(a,b); i++) cyc[i]=false; } return mx; } signed main() { // Input: ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n>>m; vector<int> conv(n+1); paved.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]; } vector<bool> cyc(n+1); cout << sum-dp(cyc, 0) << "\n"; return 0; }
#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...
#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...