oj.uz

Submission #487066

# Submission time Handle Problem Language Result Execution time Memory
487066 2021-11-14T03:43:07 Z XII Training (IOI07_training) C++17
100 / 100
 9 ms 2564 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "IOI07_training"
void Fi(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp", "r", stdin);
        freopen(PROB".out", "w", stdout);
    }
}

const int N = 1e3 + 1;
int n, m;
vector<int> adj[N];
int h[N], finish[N], leaveTime;
using pi = pair<int, int>;
pi p[N];
struct edge{
    int u, v, w;
    int lca;
    const bool operator<(const edge &ot){
        return finish[lca] < finish[ot.lca];
    }
};
vector<edge> ed;
vector<edge> pass[N];

int totCost = 0;

void enter(){
    cin >> n >> m;
    ed.resize(m);
    for(auto &x: ed){
        cin >> x.u >> x.v >> x.w;
        if(!x.w){
            adj[x.u].eb(x.v);
            adj[x.v].eb(x.u);
        } else totCost += x.w;
    }
}

void dfs(int u){
    FOR(i, 0, adj[u].size() - 1){
        if(adj[u][i] == p[u].fi){
            swap(adj[u][i], adj[u][adj[u].size() - 1]);
            break;
        }
    } /// adj[u].back() is parent of u
    FOR(i, 0, adj[u].size() - 1){
        int v = adj[u][i];
        h[v] = h[u] + 1;
        p[v] = {u, 1 << i};
        dfs(v);
    }
    finish[u] = ++leaveTime;
}

void calcLCA(){
    for(auto &E: ed){
        int u = E.u, v = E.v;
        if(h[u] < h[v]) swap(u, v);
        while(h[u] != h[v]) u = p[u].fi;
        while(p[u].fi != p[v].fi){
            u = p[u].fi;
            v = p[v].fi;
        }
        E.lca = (u == v ? u : p[u].fi);
    }
}

void init(){
    adj[1].eb(0);
    dfs(1);
    calcLCA();
    sort(ALL(ed));
}

int dp[N][1 << 9];

void solve(){
    for(auto E: ed){
        int L = (h[E.lca] - h[E.u]) + (h[E.lca] - h[E.v]);
        if(E.w && (L & 1)) continue;
        int V = E.lca;
        pi u = {E.u, 0}, v = {E.v, 0};
        int tmp = E.w;
        while(u.fi != V){
            tmp += dp[u.fi][u.se];
            u = p[u.fi];
        }
        while(v.fi != V){
            tmp += dp[v.fi][v.se];
            v = p[v.fi];
        }
        int N = adj[V].size() - 1;

//        cout << E.u << " " << E.v << " " << E.w << " " << V << ": ";
//        cout << N << " " << tmp << "\n";

        FORD(mask, (1 << N) - 1, 0){
            if((mask & u.se) || (mask & v.se)) continue;
            dp[V][mask] = max(dp[V][mask], tmp + dp[V][mask | u.se | v.se]);
        }
    }
}

int main(){
    IOS;
    Fi();
    enter();
    init();
    solve();
    cout << totCost - dp[1][0];
    return 0;
}

Compilation message

training.cpp: In function 'void dfs(int)':
training.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
      |                                         ^
training.cpp:56:5: note: in expansion of macro 'FOR'
   56 |     FOR(i, 0, adj[u].size() - 1){
      |     ^~~
training.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
      |                                         ^
training.cpp:62:5: note: in expansion of macro 'FOR'
   62 |     FOR(i, 0, adj[u].size() - 1){
      |     ^~~
training.cpp: In function 'void Fi()':
training.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
training.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2508 KB Output is correct
2 Correct 5 ms 2508 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 588 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 2 ms 1228 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1792 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 3 ms 1228 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 3 ms 1228 KB Output is correct
3 Correct 9 ms 2508 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1740 KB Output is correct
2 Correct 8 ms 2564 KB Output is correct
3 Correct 5 ms 1400 KB Output is correct
4 Correct 4 ms 1228 KB Output is correct