oj.uz

Submission #899355

# Submission time Handle Problem Language Result Execution time Memory
899355 2024-01-05T20:43:03 Z Nonoze Training (IOI07_training) C++17
20 / 100
 73 ms 32604 KB 
#include <bits/stdc++.h>

#define int long long
#define sz(x) (int)(x.size())

using namespace std;

const int LOG=12;

int n, k, m;

//LSONE

int LSOne(int i) {
    return i&(-i);
}


//LCA
vector<vector<int>> child;
vector<vector<int>> up;
vector<int> depth;

void dfs(int s, int last=-1) {
    for (auto u: child[s]) {
        if (u==last) continue;
        depth[u]=depth[s]+1;

        up[u][0]=s;
        for (int i=1; i<LOG; i++) {
            up[u][i]=up[ up[u][i-1] ][ i-1 ];
        }

        dfs(u, s);
    }
}

int getlca(int a, int b) {
    if (a==b) return a;
    if (depth[a] < depth[b]) swap(a, b);
    int k = depth[a] - depth[b];
    for (int j = LOG-1; j >= 0; j--) {
        if (k & (1<<j)) {
            a=up[a][j];
        }
    }
    if (a==b) return a;

    for (int j = LOG-1; j >= 0; j--) {
        if (up[a][j] != up[b][j]) {
            a=up[a][j];
            b=up[b][j];
        }
    }
    return up[a][0];
}

//DP
vector<vector<int>> memo;
vector<vector<pair<pair<int, int>, int>>> adj;
vector<vector<pair<int, int>>> passepar;
vector<vector<int>> memo2;

int dp(int s, int mask) {
    if (__builtin_popcount(mask)>=child[s].size()) return 0;
    if (memo[s][mask]!=-1) return memo[s][mask];
    int ans=0;
    for (auto u: child[s]) {
        ans=max(ans, dp(u, 0));
    }
    for (auto u: adj[s]) {
        int a=u.first.first, b=u.first.second, c=u.second;
        int temp=mask;
        bool flag=false;
        while (temp>0) {
            int lsone=LSOne(temp);
            if (passepar[a][b].first==child[s][log2(lsone)]) flag=true;
            if (passepar[a][b].second==child[s][log2(lsone)]) flag=true;
            temp-=lsone;
        }
        if (flag) continue;
        int sum=0;
        int tempmask=mask;
        if (a!=s) sum+=dp(a, 0);
        while (a!=s) {
            int prec=a;
            a=up[a][0];
            int bitmask=0;
            for (int i=0; i<sz(child[a]); i++) {
                if (child[a][i]==prec) {
                    bitmask+=(1<<i);
                }
            }
            if (a==s) tempmask|=bitmask;
            else sum+=dp(a, bitmask);
        }

        if (b!=s) sum+=dp(b, 0);
        while (b!=s) {
            int prec=b;
            b=up[b][0];
            int bitmask=0;
            for (int i=0; i<sz(child[b]); i++) {
                if (child[b][i]==prec) {
                    bitmask+=(1<<i);
                }
            }
            if (b==s) bitmask|=tempmask;
            sum+=dp(b, bitmask);
        }
        ans=max(ans, sum+c);
    }
    return memo[s][mask]=ans;
}

void solve() {
    cin >> n >> m;
    memo.clear();
    memo.resize(n, vector<int>(1<<10, -1));
    memo2.clear();
    memo2.resize(n, vector<int>(n, -1));
    passepar.clear();
    passepar.resize(n, vector<pair<int, int>>(n));
    adj.clear();
    adj.resize(n);
    child.clear();
    child.resize(n);
    up.clear();
    up.resize(n, vector<int>(LOG));
    depth.clear();
    depth.resize(n);
    vector<pair<pair<int, int>, int>> temp;
    for (int i=0; i<m; i++) {
        int u, v, c; cin >> u >> v >> c;
        u--, v--;
        if (c==0) {
            child[u].push_back(v);
            child[v].push_back(u);
        } else {
            temp.push_back({{u, v}, c});
        }
    }
    depth[0]=0;
    dfs(0);
    for (int s=0; s<n; s++) {
        for (int i=0; i<sz(child[s]); i++) {
            auto u=child[s][i];
            if (u==up[s][0]) {
                child[s].erase(child[s].begin()+i);
            }
        }
    }
    int ans=0;
    for (int i=n-1; i<m; i++) {
        int u=temp[i-n+1].first.first, v=temp[i-n+1].first.second;
        int c=temp[i-n+1].second;
        int lca=getlca(u, v);
        if (u!=v && (depth[u]+depth[v]-2*depth[lca])%2==0) {
            adj[lca].push_back({{u, v}, c});
            int a=-1, b=-1;
            for (auto s: child[lca]) {
                if (getlca(s, u)==s) {
                    if (a==-1) a=s;
                    else b=s;
                }
                if (getlca(s, v)==s) {
                    if (a==-1) a=s;
                    else b=s;
                }
            }
            passepar[u][v]={a, b};
        }
        ans+=c;
    }
    cout << ans-dp(0, 0) << endl;
    return;
}


signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt=1;// cin >> tt;
    while(tt--) solve();
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 32444 KB Output is correct
2 Correct 18 ms 32344 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 32344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 10440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 32604 KB Output isn't correct
2 Halted 0 ms 0 KB -