Submission #753631

#TimeUsernameProblemLanguageResultExecution timeMemory
753631keta_tsimakuridzeTraining (IOI07_training)C++14
10 / 100
1076 ms11604 KiB
#include<bits/stdc++.h> #define f first #define s second #define int long long #define pii pair<int,int> using namespace std; const int N = 2e5 + 5, mod = 1e9 + 7; // ! int t, in[N], out[N], timer, P[N][20], dp[N], fw[N], h[N]; vector<int> V[N]; vector<pair<pair<int,int>, int> > x[N]; void dfs0(int u, int p) { in[u] = ++timer; h[u] = h[p] + 1; P[u][0] = p; for(int i = 1; i <= 18; i++) P[u][i] = P[P[u][i - 1]][i - 1]; for(int i = 0; i < V[u].size(); i++) { int v = V[u][i]; if(v != p) dfs0(v, u); } out[u] = timer; } bool check(int u, int v) { return (in[u] <= in[v] && out[v] <= out[u]); } int lca(int u, int v) { if(check(u, v)) return u; if(check(v, u)) return v; for(int i = 18; i >= 0; i--) { if(P[u][i] && !check(P[u][i], v)) u = P[u][i]; } return P[u][0]; } int n; void upd(int id, int x) { for(id; id <= n; id += id & (-id)) fw[id] += x; } int get(int id) { int ans = 0; for(id; id >= 1; id -= id & (-id)) ans += fw[id]; return ans; } int up(int u, int x) { for(int i = 0; i <= 18; i++) { if((1 << i) & x) u = P[u][i]; } return u; } void dfs(int u, int p) { int tot = 0; for(int i = 0; i < V[u].size(); i++) { if(V[u][i] != p) dfs(V[u][i], u), tot += dp[V[u][i]]; } vector<vector<int>> bad; bad.resize((int)x[u].size(), vector<int> ((int)x[u].size())); for(int i = 0; i < (int)x[u].size(); i++) { for(int j = 0; j < (int)x[u].size(); j++) { if(i == j) continue; bad[i][j] = (lca(x[u][i].f.f, x[u][j].f.f) != u || lca(x[u][i].f.f, x[u][j].f.s) != u || lca(x[u][i].f.s, x[u][j].f.f) != u || lca(x[u][i].f.s, x[u][j].f.s) != u ); } } dp[u] = 0; for(int mask = 0; mask < (1 << (int)x[u].size()); mask++) { vector<int> v; int F = 0, cur = 0; for(int i = 0; i < (int)x[u].size(); i++) { if((1 << i) & mask) { if(x[u][i].f.f != u) v.push_back(x[u][i].f.f); if(x[u][i].f.s != u) v.push_back(x[u][i].f.s); for(int j = 0; j < (int)x[u].size(); j++) { if((1 << j) & mask) F |= bad[i][j]; } cur += x[u][i].s; } } if(F) continue; cur += tot; for(int i = 0; i < v.size(); i++) { cur -= dp[up(v[i], h[v[i]] - h[u] - 1)]; cur += get(in[v[i]]); } dp[u] = max(dp[u], cur); } for(int i = 0; i < V[u].size(); i++) { if(V[u][i] == p) continue; upd(in[V[u][i]], tot - dp[V[u][i]]); upd(out[V[u][i]] + 1, -(tot - dp[V[u][i]])); } upd(in[u], dp[u]); upd(in[u] + 1, -dp[u]); } main(){ int m; cin >> n >> m; vector<pair<pair<int,int>, int> > e; while(m--) { int u, v, c; cin >> u >> v >> c; if(!c) V[u].push_back(v), V[v].push_back(u); else { e.push_back({{u, v}, c}); } } dfs0(1, 0); int ans = 0, all = 0; for(int i = 0; i < e.size(); i++) { int u = e[i].f.f, v = e[i].f.s, c = e[i].s; if((h[u] + h[v] - 2 * h[lca(u, v)]) % 2) { ans += c; continue; } all += c; x[lca(u, v)].push_back({{u, v}, c}); } dfs(1, 0); cout << all - dp[1] + ans; }

Compilation message (stderr)

training.cpp: In function 'void dfs0(long long int, long long int)':
training.cpp:16:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
training.cpp: In function 'void upd(long long int, long long int)':
training.cpp:36:9: warning: statement has no effect [-Wunused-value]
   36 |     for(id; id <= n; id += id & (-id)) fw[id] += x;
      |         ^~
training.cpp: In function 'long long int get(long long int)':
training.cpp:40:9: warning: statement has no effect [-Wunused-value]
   40 |     for(id; id >= 1; id -= id & (-id)) ans += fw[id];
      |         ^~
training.cpp: In function 'void dfs(long long int, long long int)':
training.cpp:51:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
training.cpp:83:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(int i = 0; i < v.size(); i++) {
      |                        ~~^~~~~~~~~~
training.cpp:89:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
training.cpp: At global scope:
training.cpp:97:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   97 | main(){
      | ^~~~
training.cpp: In function 'int main()':
training.cpp:111:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(int i = 0; i < e.size(); i++) {
      |                    ~~^~~~~~~~~~
#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...