oj.uz

답안 #1018102

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1018102 2024-07-09T14:21:28 Z Cookie Training (IOI07_training) C++14
100 / 100
 9 ms 8688 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
const int cox[4] = {1, 0, -1, 0};
const int coy[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 7, pr = 31;
const int mxn = 1e3 + 5, mxs = 3e5 * 50, sq = 500, mxv = 2e6 + 1;
const int max_iter = 8e4, global_iter = 15e5 + 5;
//const int base = (1 <<18);
const ll inf = 1e9 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct E{
    int u, v, w;
};
int n, m;
int dep[mxn + 1], up[mxn + 1][11], mask[mxn + 1][mxn + 1], pa[mxn + 1];
int dp[mxn + 1][(1 << 10)];
vt<int>adj[mxn + 1];
vt<E>edge, queries[mxn + 1];
void ckmax(int &a, int b){
    if(a < b)a = b;
}
void prep(int s, int pre){
    for(auto i: adj[s]){
        if(i != pre){
            dep[i] = dep[s] + 1; up[i][0] = pa[i] = s;
            prep(i, s);
        }
    }
}
int lca(int u, int v){
    if(dep[u] < dep[v])swap(u, v);
    int k = dep[u] - dep[v];
    for(int i = 0; i < 11; i++){
        if((k >> i) & 1)u = up[u][i];
    }
    if(u == v)return(u);
    for(int i = 10; i >= 0; i--){
        if(up[u][i] != up[v][i]){
            u = up[u][i]; v = up[v][i];
        }
    }
    return(up[u][0]);
}
void dfs(int s, int pre){
    for(auto i: adj[s]){
        if(i != pre){
            dfs(i, s);
        }
    }
    for(int i = 0; i < (1 << sz(adj[s])); i++){
        for(int j = 0; j < sz(adj[s]); j++){
            if((i >> j) & 1){
                if(adj[s][j] != pre){
                    int son = adj[s][j];
                    dp[s][i] += dp[son][(1 << sz(adj[son])) - 1];
                }
            }
        }
    }
    //dp[i][j] node i used mask j
    for(auto [u, v, w]: queries[s]){
        int tot = 0, ms = 0;
        while(u != s){
            tot += dp[u][((1 << sz(adj[u])) - 1) ^ ms]; ms = mask[pa[u]][u];
            if(pa[u] == s)break;
            u = pa[u];
        }
        ms = 0;
        while(v != s){
            tot += dp[v][((1 << sz(adj[v])) - 1) ^ ms]; ms = mask[pa[v]][v];
            if(pa[v] == s)break;
            v = pa[v];
        }
        int add = mask[s][u] | mask[s][v];
        for(int j = ((1 << sz(adj[s])) - 1); j >= 0; j--){
            if((j & add) == 0){
                ckmax(dp[s][j | add], dp[s][j] + tot + w);
            }
        }
    }
}
void solve(){
    cin >> n >> m;
    int tot = 0;
    for(int i = 0; i < m; i++){
        int a, b, c; cin >> a >> b >> c;
        if(c == 0){
            adj[a].pb(b); adj[b].pb(a);
        }else{
            edge.pb({a, b, c}); tot += c;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < sz(adj[i]); j++){
            mask[i][adj[i][j]] = (1 << j);
        }
    }
    prep(1, -1);
    for(int i = 1; i < 11; i++){
        for(int j = 1; j <= n; j++){
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    for(auto [u, v, w]: edge){
        if((dep[u] & 1) == (dep[v] & 1)){
            queries[lca(u, v)].pb({u, v, w});
        }
    }
    dfs(1, -1);
    cout << tot - dp[1][((1 << sz(adj[1])) - 1)];
}



signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("KHONG.inp", "r", stdin);
    //freopen("KHONG.out", "w", stdout);
    int tt; tt = 1;
    while(tt--)solve();
    return(0);
}

Compilation message

training.cpp: In function 'void dfs(int, int)':
training.cpp:79:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |     for(auto [u, v, w]: queries[s]){
      |              ^
training.cpp: In function 'void solve()':
training.cpp:122:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  122 |     for(auto [u, v, w]: edge){
      |              ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 6 ms 8576 KB Output is correct

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5140 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 3 ms 5672 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 7 ms 6668 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4956 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 9 ms 8688 KB Output is correct
4 Correct 3 ms 5976 KB Output is correct

Subtask #11
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7012 KB Output is correct
2 Correct 8 ms 8540 KB Output is correct
3 Correct 6 ms 8464 KB Output is correct
4 Correct 6 ms 6748 KB Output is correct