Submission #554151

#	Time	Username	Problem	Language	Result	Execution time	Memory
554151		Alexandruabcde	Training (IOI07_training)	C++14	100 / 100	68 ms	4584 KiB

training

#include <bits/stdc++.h>
#define x first.first
#define y first.second
#define cost second
#define ub(x) (x&(-x))

using namespace std;

typedef pair <pair <int, int>, int> PIII;
constexpr int NMAX = 1005;

int N, M;

vector <int> G[NMAX];
vector <PIII> Edges;
vector <int> E[NMAX];
int Dad[NMAX];

int ans;

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int i = 1; i <= M; ++ i ) {
        PIII e;
        cin >> e.x >> e.y >> e.cost;

        if (e.cost == 0) {
            G[e.x].push_back(e.y);
            G[e.y].push_back(e.x);
        }
        else {
            Edges.push_back(e);
        }
    }
}

bool viz[NMAX];

void Reset () {
    for (int i = 1; i <= N; ++ i )
        viz[i] = false;
}

bool CheckOdd (int start, int finish) {
    queue <pair <int, bool> > Q;
    Q.push({start, 0});
    viz[start] = true;

    while (!Q.empty()) {
        int nod = Q.front().first;
        bool good = Q.front().second;
        good = !good;

        Q.pop();

        for (auto it : G[nod]) {
            if (viz[it]) continue;

            viz[it] = true;
            Q.push({it, good});

            if (it == finish) return good;
        }
    }

    assert(false);
}

void Do_Direct_Graph (int Node, int dad = -1) {
    vector <int> aux;
    Dad[Node] = dad;

    for (auto it : G[Node]) {
        if (it == dad) continue;

        Do_Direct_Graph(it, Node);
        aux.push_back(it);
    }

    G[Node].clear();
    G[Node] = aux;
}

int FindLca (int a, int b) {
    Reset();
    while (a != -1) {
        viz[a] = 1;
        a = Dad[a];
    }

    while (!viz[b]) b = Dad[b];

    return b;
}

int who[2048];
void Precompute () {
    for (int i = 2; i < 2048; ++ i )
        who[i] = who[i/2] + 1;
    vector <PIII> aux;

    for (auto it : Edges) {
        ans += it.cost;

        Reset();
        if (!CheckOdd(it.x, it.y))
            aux.push_back(it);
    }

    Edges = aux;

    Do_Direct_Graph(1);
    for (int i = 0; i < Edges.size(); ++ i )
        E[FindLca(Edges[i].x, Edges[i].y)].push_back(i);
}

int dp[NMAX][2048];
int sum_of_mask[2048];

int ToNode[NMAX];
int anc[NMAX];

void ComputeToNode (int Node, int value, int commonAncestor) {
    anc[Node] = commonAncestor;
    ToNode[Node] = value + dp[Node][(1<<G[Node].size())-1];
    int mask = (1<<G[Node].size()) - 1;

    for (int i = 0; i < G[Node].size(); ++ i )
        ComputeToNode(G[Node][i], value + dp[Node][mask^(1<<i)], (commonAncestor == -1 ? i : commonAncestor));
}

void Solve (int Node) {
    for (int i = 0; i < G[Node].size(); ++ i )
        Solve(G[Node][i]);
    ComputeToNode(Node, 0, -1);

    for (int mask = 1; mask < (1<<G[Node].size()); ++ mask ) {
        int last_son_ind = who[ub(mask)];
        sum_of_mask[mask] = sum_of_mask[mask-ub(mask)] + dp[G[Node][last_son_ind]][(1<<G[G[Node][last_son_ind]].size())-1];
        dp[Node][mask] = sum_of_mask[mask];

        for (auto it : E[Node]) {
            int a = Edges[it].x;
            int b = Edges[it].y;
            int c = Edges[it].cost;

            if (b == Node) swap(a, b);

            if (a == Node) {
                if (!(mask&(1<<anc[b]))) continue;

                dp[Node][mask] = max(dp[Node][mask], dp[Node][(mask^(1<<anc[b]))] + c + ToNode[b]);
            }
            else {
                if (!(mask&(1<<anc[a])) || (!(mask&(1<<anc[b])))) continue;

                int state = (mask^(1<<anc[a])^(1<<anc[b]));
                dp[Node][mask] = max(dp[Node][mask], dp[Node][state] + c + ToNode[a] + ToNode[b]);
            }
        }
    }
}

int main () {
    Read();
    Precompute();
    Solve(1);

    cout << ans - dp[1][(1<<(G[1].size()))-1] << '\n';

    return 0;
}

Compilation message (stderr)

training.cpp: In function 'void Precompute()':
training.cpp:117:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for (int i = 0; i < Edges.size(); ++ i )
      |                     ~~^~~~~~~~~~~~~~
training.cpp: In function 'void ComputeToNode(int, int, int)':
training.cpp:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for (int i = 0; i < G[Node].size(); ++ i )
      |                     ~~^~~~~~~~~~~~~~~~
training.cpp: In function 'void Solve(int)':
training.cpp:137:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for (int i = 0; i < G[Node].size(); ++ i )
      |                     ~~^~~~~~~~~~~~~~~~

• 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