Submission #625177

# Submission time Handle Problem Language Result Execution time Memory
625177 2022-08-09T14:26:55 Z keta_tsimakuridze Training (IOI07_training) C++14
0 / 100
13 ms 15108 KB
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int p[N][20], dp[N], tmin[N], tmout[N], timer, UP[N];
vector<int> t[N];
vector<int> x[N];
vector<pair<pii,int >> E[N];
bool check(int u, int v) {
    return (tmin[u] <= tmin[v] && tmout[u] >= tmout[v]);
}
int lca(int u, int v) {
    if(check(u, v)) return u;
    if(check(v, u)) return v;

    for(int i = 16; i >= 0; i--) {
        if(p[u][i] && !check(p[u][i], v)) v = p[u][i];
    }
    return p[u][0];
}
void dfs1(int u, int P) {
    tmin[u] = ++timer;
    p[u][0] = P;
    for(int i = 1; i <= 16; i++) p[u][i] = p[p[u][i - 1]][i - 1];
    for(int i = 0; i < t[u].size(); i++) {
        if(t[u][i] == P) continue;
        UP[t[u][i]] = i;
        p[t[u][i]][0] = u;
        dfs1(t[u][i], u);
    }
    tmout[u] = timer;
}
int up(int a, int u) {
    int ans = (a == u ? 0 : dp[a]);
    vector<int> v;
    while(a != u) {
        v.push_back(a);
        a = p[a][0];

    }
    return ans;
}

int get(int l, int a, int b) {
    int x = 0;
    for(int i = 0; i < t[l].size(); i++) {
        if(t[l][i] != p[l][0] && check(t[l][i], a)) x += 1 << i;
        if(t[l][i] != p[l][0] && check(t[l][i], b)) x += 1 << i;
    }
    return x;
}
void dfs(int u, int p) {
    for(int i = 0; i < t[u].size(); i++) {
        if(t[u][i] == p) continue;
        dfs(t[u][i], u);
        dp[u] = max(dp[u], dp[t[u][i]]);
    }
    x[u].resize(1 << (int)t[u].size());
    for(int j = 0; j < E[u].size(); j++) {
        int a = E[u][j].f.f, b = E[u][j].f.s, c = E[u][j].s;
        // u dan zevit


        if(b == u) swap(a, b);
        dp[u] = max(dp[u], dp[b] + c);
        return;
        c += up(a, u) + up(b, u);
        int bb = get(u, a, b);
        assert(up(a, u) >= 0); assert(up(b, u) >= 0);
        for(int mask = (1 << (int)t[u].size()) - 1; mask >= 0; --mask) {
            if(!(mask & bb))
            x[u][mask + bb] = max(x[u][mask + bb], x[u][mask] + c);
        }
    }
    for(int mask = 0; mask < (1 << (int)t[u].size()); ++mask) {

        for(int i = 0; i < t[u].size(); ++i) if(mask & (1 << i)) x[u][mask] = max(x[u][mask], x[u][mask ^ (1 << i)]);
    }
    for(int mask = 0; mask < (1 << (int)t[u].size()); ++mask) {
        int cur = x[u][mask];
        for(int i = 0; i < t[u].size(); i++) {
            if(t[u][i] == p) continue;
            if(!(mask& (1 << i))) x[u][mask ^ (1 << i)] = max(x[u][mask ^ (1 << i)] , x[u][mask] + dp[t[u][i]]);
        }
        dp[u] = max(dp[u], x[u][mask]);
    }


}
main(){
    int n, m, cost = 0;
    cin >> n >> m;
    vector<pair<pii,int> > e;
    for(int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        if(!c) t[u].push_back(v), t[v].push_back(u);
        else e.push_back({{u, v}, c});
        cost += c;
    }

    dfs1(1, 0);

    for(int i = 0; i < e.size(); ++i) {

        int u = e[i].f.f, v = e[i].f.s, c = e[i].s;
        E[lca(u, v)].push_back({{u, v}, c});
    }

    dfs(1, 1);

    cout << cost - dp[1];
 }

Compilation message

training.cpp: In function 'void dfs1(long long int, long long int)':
training.cpp:28:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i = 0; i < t[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
training.cpp: In function 'long long int get(long long int, long long int, long long int)':
training.cpp:49:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i = 0; i < t[l].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
training.cpp: In function 'void dfs(long long int, long long int)':
training.cpp:56:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i = 0; i < t[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
training.cpp:62:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int j = 0; j < E[u].size(); j++) {
      |                    ~~^~~~~~~~~~~~~
training.cpp:80:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int i = 0; i < t[u].size(); ++i) if(mask & (1 << i)) x[u][mask] = max(x[u][mask], x[u][mask ^ (1 << i)]);
      |                        ~~^~~~~~~~~~~~~
training.cpp:84:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(int i = 0; i < t[u].size(); i++) {
      |                        ~~^~~~~~~~~~~~~
training.cpp:83:13: warning: unused variable 'cur' [-Wunused-variable]
   83 |         int cur = x[u][mask];
      |             ^~~
training.cpp: At global scope:
training.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   93 | main(){
      | ^~~~
training.cpp: In function 'int main()':
training.cpp:107:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i = 0; i < e.size(); ++i) {
      |                    ~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14400 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14368 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14856 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14404 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14468 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 14676 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 15000 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 15108 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 15060 KB Output isn't correct
2 Halted 0 ms 0 KB -