Submission #708083

#TimeUsernameProblemLanguageResultExecution timeMemory
708083cig32Training (IOI07_training)C++17
30 / 100
3 ms720 KiB
#include "bits/stdc++.h" using namespace std; #define int long long const int MAXN = 2e5 + 10; const int MOD = 1e9 + 7; mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count()); int rnd(int x, int y) { int u = uniform_int_distribution<int>(x, y)(rng); return u; } int bm(int b, int p) { if(p==0) return 1 % MOD; int r = bm(b, p >> 1); if(p&1) return (((r*r) % MOD) * b) % MOD; return (r*r) % MOD; } int inv(int b) { return bm(b, MOD-2); } int fastlog(int x) { return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1); } void printcase(int i) { cout << "Case #" << i << ": "; } void solve(int tc) { int n, m; cin >> n >> m; vector<int> chain[n+1]; vector<pair<int,int> > adj[n+1]; int tcost = 0; for(int i=0; i<m; i++) { int a, b, c; cin >> a >> b >> c; if(a == b) continue; tcost += c; if(c == 0) { chain[a].push_back(b); chain[b].push_back(a); } else { adj[a].push_back({b, c}); adj[b].push_back({a, c}); } } vector<int> ord; int st; for(int i=1; i<=n; i++) if(chain[i].size() == 1) st = i; ord.push_back(st); int vis[n+1]; for(int i=1; i<=n; i++) vis[i] = 0; for(int i=1; i<n; i++) { vis[st] = 1; for(int x: chain[st]) { if(!vis[x]) { st = x; break; } } ord.push_back(st); } int dp[n+1]; for(int i=1; i<=n; i++) dp[i] = vis[i] = 0; int ma = 0; int it = 0; for(int x: ord) { vis[x] = ++it; for(pair<int, int> y: adj[x]) { if(vis[y.first] > 0 && (vis[x] - vis[y.first]) % 2 == 0) { for(int j=0; j<vis[y.first]; j++) dp[x] = max(dp[x], dp[ord[j]] + y.second); } } ma = max(ma, dp[x]); } cout << tcost - ma << '\n'; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; for(int i=1; i<=t; i++) solve(i); } /* 6 7 1 2 0 2 3 0 3 4 0 4 5 0 5 6 0 1 3 2 4 6 1 */
#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...