oj.uz

Submission #1052615

# Submission time Handle Problem Language Result Execution time Memory
1052615 2024-08-10T17:35:01 Z handlename Training (IOI07_training) C++17
100 / 100
 7 ms 4700 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define float long double
// const int MOD=1e9+7;
const int MOD=998244353;
const int sqn=450;
const long double eps=1e-6;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
long long power(long long a,long long b,long long p=MOD){
    long long res=1;
    while (b>0){
        if (b%2==1) res=(res*a)%p;
        b/=2;
        a=(a*a)%p;
    }
    return res;
}
int n,m,sum;
vector<int> adj[1001],children[1001];
vector<pair<pair<int,int>,int> > edges[1001];
int twok[1001][11],depth[1001],childid[1001];
void dfsfill(int x,int p,int dd){
    twok[x][0]=p;
    depth[x]=dd;
    for (int i=1;i<11;i++){
        if (twok[x][i-1]==-1) break;
        twok[x][i]=twok[twok[x][i-1]][i-1];
    }
    int id=0;
    for (auto i:adj[x]){
        if (i==p) continue;
        dfsfill(i,x,dd+1);
        children[x].pb(i);
        childid[i]=id;
        id++;
    }
}
int lcaa(int a,int b){
    if (depth[a]<depth[b]) swap(a,b);
    int dd=depth[a]-depth[b];
    for (int i=0;i<11;i++){
        if (dd&(1<<i)){
            a=twok[a][i];
        }
    }
    if (a==b) return a;
    for (int i=10;i>=0;i--){
        if (twok[a][i]!=twok[b][i]){
            a=twok[a][i];
            b=twok[b][i];
        }
    }
    return twok[a][0];
}
// start from graph containing only tree edges
// add max weight nontree edges without even cycles
// tree path of edge (A,B) consists of only tree edges
// odd/even edges have odd/even length tree path
// we can only take even edges
// no 2 nontree edges can have tree path overlap
// otherwise, odd path 1 + odd path 2 - overlap * 2 = even
// hence, each tree edge is in max 1 odd cycle
// we solve for every subtree
// dp[index][mask] = max weight we can take
// index = subtree root
// mask = which of the root's children is removed
// basically we have a tree
// each nontree edge is like placing a weight on a path
// we need to maximise the sum of weights without overlaps
int dp[1001][1024];
void dfs(int x){
    for (auto i:children[x]){
        dfs(i);
    }
    int sz=children[x].size();
    for (int i=0;i<(1<<sz);i++){
        for (int j=0;j<sz;j++){
            if (i&(1<<j)) continue;
            // since mask is who we want to exclude
            dp[x][i]+=dp[children[x][j]][0];
        }
    }
    for (auto edge:edges[x]){
        int a=edge.first.first;
        int b=edge.first.second;
        int cur=edge.second;
        int maska=0;
        while (a!=x){
            cur+=dp[a][maska];
            maska=(1<<childid[a]);
            a=twok[a][0];
        }
        int maskb=0;
        while (b!=x){
            cur+=dp[b][maskb];
            maskb=(1<<childid[b]);
            b=twok[b][0];
        }
        int mask=maska|maskb;
        for (int i=0;i<(1<<sz);i++){
            if (i&mask) continue;
            dp[x][i]=max(dp[x][i],cur+dp[x][i|mask]);
        }
    }
}
void runtc(){
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if (c==0){
            adj[a].pb(b);
            adj[b].pb(a);
        }
        else {
            edges[0].pb(mp(mp(a,b),c));
        }
        sum+=c;
    }
    dfsfill(1,-1,0);
    for (auto i:edges[0]){
        int a=i.first.first;
        int b=i.first.second;
        int c=i.second;
        if ((depth[a]%2)!=(depth[b]%2)) continue;
        int lca=lcaa(a,b);
        edges[lca].pb(mp(mp(a,b),c));
    }
    dfs(1);
    cout<<sum-dp[1][0];
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("movie.in","r",stdin);
    // freopen("movie.out","w",stdout);
    // freopen("input1.in","r",stdin);
    // freopen("output1.out","w",stdout);
    //freopen("tower_rush_input.txt","r",stdin);
    //freopen("hackercup_output.txt","w",stdout);
    int tcs;
    // cin>>tcs;
    tcs=1;
    for (int i=1;i<=tcs;i++){
        // cout<<"Case #"<<i<<": ";
        runtc();
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 4 ms 4700 KB Output is correct

Subtask #4
7.0 / 7.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 #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 1628 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 3 ms 1456 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB Output is correct
2 Correct 1 ms 1700 KB Output is correct
3 Correct 6 ms 4700 KB Output is correct
4 Correct 2 ms 1884 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2148 KB Output is correct
2 Correct 7 ms 4700 KB Output is correct
3 Correct 4 ms 3348 KB Output is correct
4 Correct 3 ms 1372 KB Output is correct