Submission #753878

#	Time	Username	Problem	Language	Result	Execution time	Memory
753878		keta_tsimakuridze	Training (IOI07_training)	C++14	10 / 100	1082 ms	6204 KiB

training

#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 = 1000 + 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[x].size()) - 1 - (1 << edge[x])];
            if(P[x][0] == u) UP[x] = x;
            else UP[x] = UP[P[x][0]];
        }
    }
    vector<vector<int>> bad;
    bad.resize(x[u].size(), vector<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);
        }
    }
    for(int i = 0; i < (1 << (int)x[u].size()); i++) {
        int F = 0, mask = 0, ans = 0;
        for(int j = 0; j < x[u].size(); j++) {
            if(((1 << j) & i) == 0) continue;
            for(int k = 0; k < x[u].size(); k++) {
                if((1 << k) & i) F |= bad[j][k];
            }
            if(x[u][j].f.f != u) mask |= 1 << edge[UP[x[u][j].f.f]], ans += dp_[x[u][j].f.f];
            if(x[u][j].f.s != u) mask |= 1 << edge[UP[x[u][j].f.s]], ans += dp_[x[u][j].f.s];
            ans += x[u][j].s;
        }
        if(F) continue;
        dp[u][mask] = max(dp[u][mask], ans);

    }
    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]));
        }
    }
//    cout << u << " ++ " << all(u) << endl;
}
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});
        }
    }
    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:46: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]
   46 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
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.size(); i++) {
      |                    ~~^~~~~~~~~~
training.cpp:71: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]
   71 |         for(int j = 0; j < x[u].size(); j++) {
      |                        ~~^~~~~~~~~~~~~
training.cpp:73:30: 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]
   73 |             for(int k = 0; k < x[u].size(); k++) {
      |                            ~~^~~~~~~~~~~~~
training.cpp:85: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]
   85 |         for(int j = 0; j < V[u].size(); j++) {
      |                        ~~^~~~~~~~~~~~~
training.cpp: At global scope:
training.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main(){
      | ^~~~
training.cpp: In function 'int main()':
training.cpp:106: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]
  106 |     for(int i = 0; i < e.size(); i++) {
      |                    ~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9