Submission #512636

#	Time	Username	Problem	Language	Result	Execution time	Memory
512636		blue	Training (IOI07_training)	C++17	100 / 100	33 ms	1612 KiB

training

#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
 
const int maxN = 1'000;
const int logN = 10;
 
using vi = vector<int>;
using pii = pair<int, int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())
 
struct trail
{
    int a;
    int b;
    int c;
};
 
int N, M;
vector<trail> trails;
vi edge[1+maxN];
 
 
vi par(1+maxN, 0);
vvi anc(1+maxN, vi(1+logN, 0));
vector< vector< vi > > desc(1+maxN, vector<vi>(1+logN));
vi depth(1+maxN, 0);
 
void dfs(int u)
{
    for(int v: edge[u])
    {
        if(v == par[u]) continue;
        par[v] = u;
        depth[v] = 1 + depth[u];
        dfs(v);
    }
}
 
int ancestor(int u, int k)
{
    for(int e = 0; e <= logN; e++)
        if(k & (1 << e))
            u = anc[u][e];
 
    return u;
}
 
int lca(int u, int v)
{
    if(depth[u] > depth[v]) swap(u, v);
 
    v = ancestor(v, depth[v] - depth[u]);
 
    if(u == v) return u;
 
    for(int e = logN; e >= 0; e--)
    {
        if(anc[u][e] == anc[v][e]) continue;
        u = anc[u][e];
        v = anc[v][e];
    }
 
    return anc[u][0];
}
 
struct vtrail
{
    int v;
    int c;
};
 
vector<vtrail> v_trails[1+maxN];
vector<trail> h_trails[1+maxN];
 
int basicCost = 0;
int defaultCost = 0;
 
 
 
 
vi strict(1+maxN, 0);
vi loose(1+maxN, 0);
 
vvi loose_lift(1+maxN, vi(1+logN, 0));
vi child_loose_sum(1+maxN, 0);
 
vvi dp(1+maxN);
 
int loose_query(int u, int k)
{
    int ans = 0;
    for(int e = 0; e <= logN; e++)
    {
        if(k & (1 << e))
        {
            ans += loose_lift[u][e];
            u = anc[u][e];
        }
    }
    return ans;
}
 
void binary_lift(int u, int e)
{
    loose_lift[u][e] = loose_lift[anc[u][e-1]][e-1] + loose_lift[u][e-1];
    for(int v: desc[u][e])
        binary_lift(v, e+1);
}
 
vi inv_pow(2000);
 
vi child_ind(1+maxN);
 
void final_dfs(int u)
{
    for(int v: desc[u][0])
    {
        final_dfs(v);
        child_loose_sum[u] += loose[v];
    }
    int z = sz(desc[u][0]);
    if(z > 0)
    {
        dp[u] = vi((1<<z), 0);
 
        for(int i = 0; i < z; i++)
            child_ind[desc[u][0][i]] = i;
 
        vi trail_occ[z];
 
        int tz = sz(h_trails[u]);
 
        vi lc(tz), rc(tz);
        for(int i = 0; i < tz; i++)
        {
 
            lc[i] = child_ind[ancestor(h_trails[u][i].a, depth[h_trails[u][i].a] - depth[u] - 1)];
 
            rc[i] = child_ind[ancestor(h_trails[u][i].b, depth[h_trails[u][i].b] - depth[u] - 1)];
 
 
            if(lc[i] > rc[i]) swap(lc[i], rc[i]);
 
            trail_occ[lc[i]].push_back(i);
            trail_occ[rc[i]].push_back(i);
        }
 
        dp[u][0] = 0;
 
        for(int mask = 1; mask < (1<<z); mask++)
        {
            if(mask == (mask & -mask))
            {
                dp[u][mask] = loose[ desc[u][0][ inv_pow[mask] ] ];
            }
            else
            {
                int lb = inv_pow[mask & -mask];
                dp[u][mask] = dp[u][mask - (mask&-mask)] + loose[ desc[u][0][lb] ];
 
                for(int ti: trail_occ[lb])
                {
                    if(!(mask & (1 << rc[ti]))) continue;
                    if(!(mask & (1 << lc[ti]))) continue;
                    int newval = dp[u][mask - (1<<lc[ti]) - (1<<rc[ti])];
 
 
                    int a = h_trails[u][ti].a;
                    int b = h_trails[u][ti].b;
                    int c = h_trails[u][ti].c;
 
                    newval += strict[a] + loose_query(a, depth[a] - depth[u] - 1);
                    newval += strict[b] + loose_query(b, depth[b] - depth[u] - 1);
                    newval += c;
                    dp[u][mask] = max(dp[u][mask], newval);
                }
            }
        }
        strict[u] = dp[u][(1<<z) - 1];
 
        for(int i = 0; i < z; i++)
        {
            int v = desc[u][0][i];
            loose_lift[v][0] = dp[u][(1<<z) - 1 - (1<<i)];
 
            for(int v2: desc[v][0])
                binary_lift(v2, 1);
        }
    }
 
    loose[u] = strict[u];
    for(vtrail vt: v_trails[u])
    {
        loose[u] = max(loose[u], loose_query(vt.v, depth[vt.v] - depth[u]) + strict[vt.v] + vt.c);
    }
}
 
 
 
 
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> N >> M;
 
    for(int e = 1; e <= M; e++)
    {
        int a, b;
        int c;
        cin >> a >> b >> c;
 
        if(c != 0) trails.push_back({a, b, c});
        else
        {
            edge[a].push_back(b);
            edge[b].push_back(a);
        }
    }
 
    dfs(1);
    for(int i = 1; i <= N; i++) anc[i][0] = par[i];
    for(int e = 1; e <= logN; e++)
        for(int i = 0; i <= N; i++)
            anc[i][e] = anc[ anc[i][e-1] ][e-1];
 
    for(int i = 0; i <= N; i++)
        for(int e = 0; e <= logN; e++)
            if(anc[i][e] != 0)
                desc[anc[i][e]][e].push_back(i);
 
 
 
    for(auto& t: trails)
    {
        if(depth[t.a] % 2 != depth[t.b] % 2)
        {
            basicCost += t.c;
            continue;
        }
 
        defaultCost += t.c;
 
        int l = lca(t.a, t.b);
 
        if(l == t.a)
        {
            v_trails[ancestor(t.b, depth[t.b] - depth[t.a] - 1)].push_back({t.b, t.c});
        }
        else if(l == t.b)
        {
            v_trails[ancestor(t.a, depth[t.a] - depth[t.b] - 1)].push_back({t.a, t.c});
        }
        else h_trails[l].push_back(t);
    }
 
    for(int e = 0; e < 10; e++)
        inv_pow[(1<<e)] = e;
 
    final_dfs(1);
 
 
    cout << basicCost + (defaultCost - strict[1]) << '\n';
}

• 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