Submission #899347

#	Time	Username	Problem	Language	Result	Execution time	Memory
899347		Nonoze	Training (IOI07_training)	C++17	20 / 100	78 ms	32604 KiB

training

#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;
        if (memo2[a][b]!=-1) {
            ans=max(ans, memo2[a][b]);
            continue;
        }
        int sum=0;
        int aa=a, bb=b;
        if (a!=s) sum+=dp(a, 0);
        int tempmask=mask;
        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 || child[a][i]==b) {
                    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 (a==s) bitmask|=tempmask;
            sum+=dp(b, bitmask);
        }
        memo2[a][b]=sum+c;
        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 (depth[s]<depth[lca]) continue;
                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;
}

Compilation message (stderr)

training.cpp: In function 'long long int dp(long long int, long long int)':
training.cpp:87:13: warning: unused variable 'aa' [-Wunused-variable]
   87 |         int aa=a, bb=b;
      |             ^~
training.cpp:87:19: warning: unused variable 'bb' [-Wunused-variable]
   87 |         int aa=a, bb=b;
      |                   ^~

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