Submission #625179

#	Time	Username	Problem	Language	Result	Execution time	Memory
625179		keta_tsimakuridze	Training (IOI07_training)	C++14	0 / 100	14 ms	15060 KiB

training

#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] << endl;
 }

Compilation message (stderr)

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) {
      |                    ~~^~~~~~~~~~

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