Submission #753992

#TimeUsernameProblemLanguageResultExecution timeMemory
753992keta_tsimakuridzeTraining (IOI07_training)C++14
100 / 100
13 ms4948 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 = 1600 + 5, mod = 1e9 + 7; // ! int t, in[N], out[N], timer, P[N][20], h[N], edge[N]; vector<int> V[N], v; int dp[N][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; v.push_back(u); 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); else { swap(V[u][i], V[u].back()); --i; V[u].pop_back(); } } 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 all(int X) { return dp[X][(1 << (int)V[X].size()) - 1]; } int n, UP[N]; void dfs(int u) { for(int i = 0; i < V[u].size(); i++) { edge[V[u][i]] = i; dfs(V[u][i]); } vector<int> dp_(n + 2); for(int i = 0; i < v.size(); i++) { if(v[i] == u) continue; if(check(u, v[i])) { int x = v[i]; dp_[x] = dp_[P[x][0]] - all(P[x][0]) + all(x) + dp[P[x][0]][(1 << V[P[x][0]].size()) - 1 - (1 << edge[x])]; if(P[x][0] == u) UP[x] = x; else UP[x] = UP[P[x][0]]; } } vector<int> mask(x[u].size()), ans(x[u].size()); for(int j = 0; j < x[u].size(); j++) { ans[j] = x[u][j].s; if(x[u][j].f.f != u) { mask[j] |= 1 << edge[UP[x[u][j].f.f]]; ans[j] += dp_[x[u][j].f.f]; } if(x[u][j].f.s != u){ mask[j] |= 1 << edge[UP[x[u][j].f.s]]; ans[j] += dp_[x[u][j].f.s]; } } for(int i = 0; i < (1 << (int)V[u].size()); i++) { for(int j = 0; j < V[u].size(); j++) { if((1 << j) & i) dp[u][i] = max(dp[u][i], dp[u][i - (1 << j)] + all(V[u][j])); } for(int j = 0; j < x[u].size(); j++) { if((mask[j] & i) == mask[j]) dp[u][i] = max(dp[u][i], dp[u][i - mask[j]] + ans[j]); } } } main(){ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); 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}); } // assert(V[u].size() <= 2); assert(V[v].size() <= 2); } int root = 1; dfs0(root, 0); int ans = 0, tot = 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; } tot += c; x[lca(u, v)].push_back({{u, v}, c}); } dfs(root); cout << tot - all(root) + ans; }

Compilation message (stderr)

training.cpp: In function 'void dfs0(long long int, long long int)':
training.cpp:17: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]
   17 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
training.cpp: In function 'void dfs(long long int)':
training.cpp:45: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]
   45 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
training.cpp:50: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]
   50 |     for(int i = 0; i < v.size(); i++) {
      |                    ~~^~~~~~~~~~
training.cpp:60: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]
   60 |     for(int j = 0; j < x[u].size(); j++) {
      |                    ~~^~~~~~~~~~~~~
training.cpp:72: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]
   72 |         for(int j = 0; j < V[u].size(); j++) {
      |                        ~~^~~~~~~~~~~~~
training.cpp:75:26: 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]
   75 |         for(int j = 0; j < x[u].size(); j++) {
      |                        ~~^~~~~~~~~~~~~
training.cpp: At global scope:
training.cpp:80:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   80 | main(){
      | ^~~~
training.cpp: In function 'int main()':
training.cpp:97: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]
   97 |     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...