Submission #708075

#TimeUsernameProblemLanguageResultExecution timeMemory
708075cig32Training (IOI07_training)C++17
0 / 100
3 ms1236 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; 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); bool vis[n+1]; for(int i=1; i<=n; i++) vis[i] = 0; set<int> bruh; bruh.insert(st); for(int i=1; i<n; i++) { vis[st] = 1; for(int x: chain[st]) { if(!vis[x]) { st = x; break; } } bruh.insert(st); ord.push_back(st); } assert(bruh.size()==n); int dp[n+1]; for(int i=1; i<=n; i++) dp[i] = vis[i] = 0; int ma = 0; for(int x: ord) { vis[x] = 1; for(pair<int, int> y: adj[x]) { if(vis[y.first]) dp[x] = max(dp[x], dp[y.first] + 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); } /* 5 8 3 2 0 4 3 0 5 4 0 1 5 0 2 4 2 4 1 2 3 5 5 3 1 1 */

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from training.cpp:1:
training.cpp: In function 'void solve(long long int)':
training.cpp:61:21: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   61 |   assert(bruh.size()==n);
      |          ~~~~~~~~~~~^~~
#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...