oj.uz

답안 #554151

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
554151 2022-04-27T17:37:02 Z Alexandruabcde Training (IOI07_training) C++14
100 / 100
 68 ms 4584 KB 
#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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 4580 KB Output is correct
2 Correct 36 ms 4584 KB Output is correct

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 504 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 4 ms 636 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 980 KB Output is correct
2 Correct 7 ms 852 KB Output is correct
3 Correct 14 ms 1492 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 2124 KB Output is correct
2 Correct 24 ms 1132 KB Output is correct
3 Correct 14 ms 1456 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 724 KB Output is correct
2 Correct 11 ms 1660 KB Output is correct
3 Correct 48 ms 4444 KB Output is correct
4 Correct 13 ms 1764 KB Output is correct

Subtask #11
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 1964 KB Output is correct
2 Correct 68 ms 4500 KB Output is correct
3 Correct 52 ms 1548 KB Output is correct
4 Correct 22 ms 1340 KB Output is correct