Submission #512518

#	Time	Username	Problem	Language	Result	Execution time	Memory
512518		blue	Training (IOI07_training)	C++17	30 / 100	14 ms	1484 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)
{
    // cerr << "ancestor " << u << ' ' << k << "\n";
    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(e & (1 << k))
        {
            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 dp;
vi child_ind(1+maxN);

void final_dfs(int u)
{
    // cerr << "enter final dfs " << u << '\n';
    for(int v: desc[u][0])
    {
        final_dfs(v);
        child_loose_sum[u] += loose[v];
    }

    // for(int v: desc[u][0])
    // {
    //     loose_lift[v][0] = child_loose_sum[u] - loose[v];
    //     for(int v2: desc[v][0])
    //         binary_lift(v2, 1);
    // }

    // cerr << "\n\n\n\n entering computations of " << u << '\n';
    //somehow compute strict
    // cerr << "A\n";
    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;

        // cerr << "u\n";

        vi trail_occ[z];

        int tz = sz(h_trails[u]);
        // cerr << "tz = " << tz << '\n';

        vi lc(tz), rc(tz);
        for(int i = 0; i < tz; i++)
        {
            // cerr << "i = " << i << '\n';
            // cerr << "val = " << h_trails[u][i].a << '\n';
            // cerr << "?\n";

            lc[i] = child_ind[ancestor(h_trails[u][i].a, depth[h_trails[u][i].a] - depth[u] - 1)];
            // cerr << "#\n";
            rc[i] = child_ind[ancestor(h_trails[u][i].b, depth[h_trails[u][i].b] - depth[u] - 1)];
            // cerr << "lc rc computed\n";

            if(lc[i] > rc[i]) swap(lc[i], rc[i]);

            trail_occ[lc[i]].push_back(i);
            // trail_occ[rc[i]].push_back(i);

            // cerr << "h trail = " << h_trails[u][i].a << ' ' << h_trails[u][i].b << ' ' << h_trails[u][i].c << '\n';
        }
        // cerr << "v\n";

        dp[u][0] = 0;

        for(int mask = 1; mask < (1<<z); mask++)
        {
            // cerr << "###\n";
            // cerr << "desc mask = " << mask << '\n';
            if(mask == (mask & -mask))
            {
                // cerr << "case 1\n";
                // cerr << inv_pow[mask] << " - " << desc[u][0][inv_pow[mask]] << " : " << loose[desc[u][0][inv_pow[mask]]] << '\n';
                dp[u][mask] = loose[ desc[u][0][ inv_pow[mask] ] ];
            }
            else
            {
                // cerr << "case 2\n";
                int lb = inv_pow[mask & -mask];
                dp[u][mask] = dp[u][mask - (mask&-mask)] + loose[ desc[u][0][lb] ];

                // cerr << "lb = " << lb << " : " << sz(trail_occ[lb]) << '\n';

                for(int ti: trail_occ[lb])
                {
                    if(!(mask & (1 << rc[ti]))) continue;
                    assert(mask & (1 << lc[ti]));
                    // cerr << "\n\n";
                    // cerr << "checking trail\n";
                    // cerr << "checking trail : " << h_trails[u][ti].a << ' ' << h_trails[u][ti].b << ' ' << h_trails[u][ti].c << '\n';
                    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 mask = 0; mask < (1 << z); mask++)
            for(int mask2 = mask; mask2 < (1 << z); mask2++)
                if((mask & mask2) == mask)
                    assert(dp[u][mask] <= dp[u][mask2]);
        // cerr << "w\n";

        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);
        }
    }
    // cerr << "B\n";



    loose[u] = strict[u];
    for(vtrail vt: v_trails[u])
    {
        // cerr << "vt = " << u << " : " << vt.v << ' ' << vt.c << '\n';
        loose[u] = max(loose[u], loose_query(vt.v, depth[vt.v] - depth[u]) + strict[vt.v] + vt.c);
    }

    // cerr << "strict, loose = " << strict[u] << ' ' << loose[u] << '\n';

    // cerr << "exit final dfs " << u << '\n';
}






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);

        // cerr << t.a << ' ' << t.b << ' ' << t.c << " : root = " << l << '\n';

        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;

    // cerr << "A\n";

    final_dfs(1);


    cout << basicCost + (defaultCost - strict[1]) << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 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