제출 #1163068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163068		kiethm07	Training (IOI07_training)	C++20	100 / 100	17 ms	8520 KiB

training

#include <bits/stdc++.h>

#define pii pair<int,int>
#define fi first
#define se second

#define all(x) (x).begin(),(x).end()
#define compact(x) (x).erase(unique(all(x)),(x).end())
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

const int inf = 1e9;
const ll linf = 1e18;
const double pi = acos(-1);
const int N = 1005;
const int M = 5005;
const int K = 10;
const int LOG = 31 - __builtin_clz(N) + 1;

struct edge{
    int u,v,w;
    edge(){}
    edge(int a,int b,int c){
        u = a, v = b, w = c;
    }
};

int dp[N][1 << K];
int sum[N][N];
int pa[N][LOG];
int h[N];
int n,m;
vector<int> a[N];
vector<edge> e;
vector<int> f[N];
vector<pii> g[N];

int lca(int u,int v){
    if (h[u] < h[v]) swap(u,v);
    int k = h[u] - h[v];
    for (int i = 0; i < LOG; i++){
        if (k & (1 << i)) u = pa[u][i];
    }
    if (u == v) return u;
    for (int i = LOG - 1; i >= 0; i--){
        if (pa[u][i] == pa[v][i]) continue;
        u = pa[u][i];
        v = pa[v][i];
    }
    return pa[u][0];
}

int getId(int u,int v){
    ///u is an ancestor of v
    int k = h[v] - h[u] - 1;
    for (int i = 0; i < LOG; i++){
        if (k & (1 << i)) v = pa[v][i];
    }
    for (int i = 0; i < a[u].size(); i++){
        int nxt = a[u][i];
        if (nxt == v) return i;
    }
    return -1;
}

void preDfs(int u,int p = -1){
    for (int i = 1; (1 << i) <= h[u]; i++){
        pa[u][i] = pa[pa[u][i - 1]][i - 1];
    }
    for (int i = 0; i < a[u].size(); i++){
        int v = a[u][i];
        if (v == p){
            a[u].erase(a[u].begin() + i);
            i--;
            continue;
        }
        h[v] = h[u] + 1;
        pa[v][0] = u;
        preDfs(v,u);
    }
}

int full(int u){
    return (1 << int(a[u].size())) - 1;
}

int dfs(int u,int mask);

int lift1(int v,int fin){
    if (v == fin) return 0;
    int res = dfs(v,full(v));
    int u = -1;
    while(1){
        int u = pa[v][0];
        if (u == fin) break;
        int id = 0;
        for (id; id < a[u].size(); id++){
            if (a[u][id] == v) break;
        }
        res += dfs(u, full(u) ^ (1 << id));
        v = u;
    }
    return res;
}

int lift(int v,int fin){
    return sum[fin][v];
}

bool valid(int id,int mask){
    if (id == -1) return 1;
    return (mask & (1 << id)) ? 1 : 0;
}

void cal(int x,int u){
    for (int i = 0; i < a[u].size(); i++){
        int v = a[u][i];
        sum[x][v] = dfs(v,full(v));
        sum[x][v] += sum[x][u];
        sum[x][v] -= dfs(u,full(u));
        sum[x][v] += dfs(u,full(u) ^ (1 << i));
        cal(x,v);
    }
}

int dfs(int u,int mask){
    if (dp[u][mask] != -1) return dp[u][mask];
    int& res = dp[u][mask];
    res = 0;
    ///not take
    for (int i = 0; i < a[u].size(); i++){
        if (!(mask & (1 << i))) continue;
        int v = a[u][i];
        res += dfs(v,full(v));
    }
    ///take
    sum[u][u] = 0;
    for (int i = 0; i < a[u].size(); i++){
        if (!(mask & (1 << i))) continue;
        int v = a[u][i];
        sum[u][v] = dfs(v,full(v));
//        res += sum[u][v];
        cal(u,v);
    }
    for (int i = 0; i < f[u].size(); i++){
        int id = f[u][i];
        int sum = e[id].w;
        int l = e[id].u;
        int x = g[u][i].fi;
        int r = e[id].v;
        int y = g[u][i].se;
        if ((!valid(x,mask)) || (!valid(y,mask))) continue;
//        assert(lift1(l,u) == lift(l,u));
//        assert(lift1(r,u) == lift(r,u));
        sum += lift(l,u) + lift(r,u);
        int newmask = mask;
        if (x != -1) newmask ^= (1 << x);
        if (y != -1) newmask ^= (1 << y);
        sum += dfs(u,newmask);
        res = max(res, sum);
    }
    return res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    #define TEXT "training"
    if (fopen(TEXT".inp","r")){
        freopen(TEXT".inp","r",stdin);
//        freopen(TEXT".out","w",stdout);
    }
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int u,v,w;
        cin >> u >> v >> w;
        if (w == 0){
            a[u].push_back(v);
            a[v].push_back(u);
        }
        else e.push_back(edge(u,v,w));
    }
    preDfs(1);
    int res = 0;
    int total = 0;
    for (int i = 0; i < e.size(); i++){
        int u = e[i].u;
        int v = e[i].v;
        int w = e[i].w;
        if ((h[u] + h[v]) & 1) res += w;
        else{
            total += w;
            int l = lca(u,v);
            f[l].push_back(i);
            int x = getId(l,u);
            int y = getId(l,v);
//            cout << u << " " << v << " " << l << " " << x << " " << y << "\n";
            g[l].push_back(pii(x,y));
        }
    }
    memset(dp,-1,sizeof(dp));
    int tmp = dfs(1,full(1));
//    cout << total << "\n";
//    cout << tmp << "\n";
    res += total - tmp;
    cout << res << "\n";
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

training.cpp: In function 'int main()':
training.cpp:174:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |         freopen(TEXT".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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