oj.uz

Submission #537796

# Submission time Handle Problem Language Result Execution time Memory
537796 2022-03-15T14:04:03 Z Lobo Beads and wires (APIO14_beads) C++17
57 / 100
 1000 ms 127312 KB 
#include<bits/stdc++.h>
using namespace std;
 
const int inf = (int) 1e9 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()


 
#define maxn 200020
 
int n;
vector<int> dp[maxn][4][2];
vector<pair<int,int>> g[maxn];

int MAX(int a, int b) {
    if(a > b) return a;
    return b;
}

/*
u = vertice
p = como esta
    0 = liga pro pai ou pra algum filho com azul e o outro azul que vai ligar para esse segundo
    3 = liga pro pai ou pra algum filho com azul e esse cara que vai ligar para o primeiro

    1 = liga pro pai com red ou nao pode mais ligar pra ninguem / ja fez sua ligacao
    2 = pode ligar para alguem com red ou para 2 com azul / ainda nao ligou pra ninguem

    
f = pode nao usar nada
    1 = tem que nao usar
    0 = tem que usar
*/

int sol(int u, int p, int f, int id, int ant) {
    if(dp[u][p][f][id] != -inf-1) return dp[u][p][f][id];
    if(p == 0) {
        //tem que ligar para alguem com azul e nao se preocupa

        //se ja tiver passado por todo mundo é -inf
        if(id == g[u].size()) return dp[u][p][f][id] = -inf;
        int v = g[u][id].fr;
        int w = g[u][id].sc;
        if(v == ant) return dp[u][p][f][id] = sol(u,p,f,id+1,ant);

        dp[u][p][f][id] = -inf;

        //se o outro azul é v
        dp[u][p][f][id] = MAX(dp[u][p][f][id], w + sol(v,2,0,0,u) + sol(u,1,f,id+1,ant));
        dp[u][p][f][id] = MAX(dp[u][p][f][id], w + sol(v,2,f,0,u) + sol(u,1,0,id+1,ant));

        //só passa para o próximo podendo ligar para ele com azul 
        //(e o outro azul que vai estar ocupado) ou red
        dp[u][p][f][id] = MAX(dp[u][p][f][id], MAX(sol(v,1,0,0,u),w+sol(v,3,0,0,u)) + sol(u,0,f,id+1,ant));
        dp[u][p][f][id] = MAX(dp[u][p][f][id], MAX(sol(v,1,f,0,u),w+sol(v,3,f,0,u)) + sol(u,0,0,id+1,ant));

        // cout << u << " ja ligou azul p = 0 || f = " << f << " atual no " << v << " id " << id << " = " << " = " << dp[u][p][f][id] << endl;
        return dp[u][p][f][id] = dp[u][p][f][id];
    }
    else if(p == 3) {
         //tem que ligar para alguem com azul e o filho azul nao pode ligar para mais ninguem

        //se ja tiver passado por todo mundo é -inf
        if(id == g[u].size()) return dp[u][p][f][id] = -inf;
        int v = g[u][id].fr;
        int w = g[u][id].sc;
        if(v == ant) return dp[u][p][f][id] = sol(u,p,f,id+1,ant);

        dp[u][p][f][id] = -inf;

        //se o outro azul é v
        dp[u][p][f][id] = MAX(dp[u][p][f][id], w + sol(v,1,0,0,u) + sol(u,1,f,id+1,ant));
        dp[u][p][f][id] = MAX(dp[u][p][f][id], w + sol(v,1,f,0,u) + sol(u,1,0,id+1,ant));

        //só passa para o próximo podendo ligar para ele com azul 
        //(e o outro azul que vai estar ocupado) ou red
        dp[u][p][f][id] = MAX(dp[u][p][f][id], MAX(sol(v,1,0,0,u),w+sol(v,3,0,0,u)) + sol(u,3,f,id+1,ant));
        dp[u][p][f][id] = MAX(dp[u][p][f][id], MAX(sol(v,1,f,0,u),w+sol(v,3,f,0,u)) + sol(u,3,0,id+1,ant));

        // cout << u << " ja ligou azul p = 3 || f = " << f << " atual no " << v << " id " << id << " = " << " = " << dp[u][p][f][id] << endl;
        return dp[u][p][f][id];
    }
    else if(p == 1) {
        //ele ja fez a ligacao entao só pode passar pro próximo
        //o v pode ligar para ele com red ou azul

        if(id == g[u].size()) {
            if(f == 1) return dp[u][p][f][id] = -inf;
            else return dp[u][p][f][id] = 0;
        }
        int v = g[u][id].fr;
        int w = g[u][id].sc;
        if(v == ant) return dp[u][p][f][id] = sol(u,p,f,id+1,ant);

        dp[u][p][f][id] = -inf;

        //só passa para o próximo podendo ligar para ele com azul 
        //(e o outro azul que vai estar ocupado) ou red
        dp[u][p][f][id] = MAX(dp[u][p][f][id], MAX(sol(v,1,0,0,u),w+sol(v,3,0,0,u)) + sol(u,1,f,id+1,ant));
        dp[u][p][f][id] = MAX(dp[u][p][f][id], MAX(sol(v,1,f,0,u),w+sol(v,3,f,0,u)) + sol(u,1,0,id+1,ant));

        // cout << u << " ja ligou para todos || f = " << f << " atual no " << v << " = " << dp[u][p][f][id] << endl;
        return dp[u][p][f][id];
    }
    else if(p == 2) {
        //ele nao ligou para ninguem ainda e se f = 1 pode continuear nao ligando

        if(id == g[u].size()) {
            if(f == 1) return dp[u][p][f][id] = 0; //ele fez a opcao de nao ligar para niguem
            else return dp[u][p][f][id] = -inf; //ele nao pode nao ligar para ninguem e mesmo assim fez
        }
        int v = g[u][id].fr;
        int w = g[u][id].sc;
        if(v == ant) return dp[u][p][f][id] = sol(u,p,f,id+1,ant);

        dp[u][p][f][id] = -inf;

        //só passa para o próximo podendo ligar para ele com azul 
        //(e o outro azul que vai estar ocupado) ou red
        dp[u][p][f][id] = MAX(dp[u][p][f][id], MAX(sol(v,1,0,0,u),w+sol(v,3,0,0,u)) + sol(u,2,f,id+1,ant));
        dp[u][p][f][id] = MAX(dp[u][p][f][id], MAX(sol(v,1,f,0,u),w+sol(v,3,f,0,u)) + sol(u,2,0,id+1,ant));

        //ele vai fazer o papel da aresta red que é quebrada pelo v
        //liga para o proximo com um uma aresta red
        dp[u][p][f][id] = MAX(dp[u][p][f][id], MAX(sol(v,2,0,0,u),w+sol(v,0,0,0,u)) + sol(u,1,f,id+1,ant));
        dp[u][p][f][id] = MAX(dp[u][p][f][id], MAX(sol(v,2,f,0,u),w+sol(v,0,f,0,u)) + sol(u,1,0,id+1,ant));

        //liga para o proximo com uma aresta azul e v que vai fazer a aresta red
        dp[u][p][f][id] = MAX(dp[u][p][f][id], w+sol(v,1,0,0,u) + sol(u,0,f,id+1,ant));
        dp[u][p][f][id] = MAX(dp[u][p][f][id], w+sol(v,1,f,0,u) + sol(u,0,0,id+1,ant));

        //liga para o proximo com uma aresta azul e o outro que vai fazer a aresta red
        dp[u][p][f][id] = MAX(dp[u][p][f][id], w+sol(v,2,0,0,u) + sol(u,3,f,id+1,ant));
        dp[u][p][f][id] = MAX(dp[u][p][f][id], w+sol(v,2,f,0,u) + sol(u,3,0,id+1,ant));

        // cout << u << " nao liga pra ninguem e || f = " << f << " atual no " << v << " = " << dp[u][p][f][id] << endl;
        return dp[u][p][f][id];
    }
    return 0;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    cin >> n;
 
    for(int i = 1; i < n; i++) {
        int u,v,w;
        cin >> u >> v >> w;
        g[u].pb(mp(v,w));
        g[v].pb(mp(u,w));
    }
 
    int rt;
    for(int i = 1; i <= n; i++) {
        if(g[i].size() == 1) {
            rt = i;
            // break;
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= g[i].size(); j++) {
            for(int k = 0; k <= 3; k++) {
                dp[i][k][0].pb(-inf-1);
                dp[i][k][1].pb(-inf-1);
            }
        }
    }
 
 
    cout << sol(rt,2,1,0,0) << endl;
}

Compilation message

beads.cpp: In function 'int sol(int, int, int, int, int)':
beads.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         if(id == g[u].size()) return dp[u][p][f][id] = -inf;
      |            ~~~^~~~~~~~~~~~~~
beads.cpp:72:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         if(id == g[u].size()) return dp[u][p][f][id] = -inf;
      |            ~~~^~~~~~~~~~~~~~
beads.cpp:95:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         if(id == g[u].size()) {
      |            ~~~^~~~~~~~~~~~~~
beads.cpp:116:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         if(id == g[u].size()) {
      |            ~~~^~~~~~~~~~~~~~
beads.cpp: In function 'int32_t main()':
beads.cpp:173:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |         for(int j = 0; j <= g[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~
beads.cpp:8:14: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
    8 | #define endl '\n'
      |              ^~~~
beads.cpp:164:9: note: 'rt' was declared here
  164 |     int rt;
      |         ^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 42592 KB Output is correct
2 Correct 22 ms 42572 KB Output is correct
3 Correct 29 ms 42592 KB Output is correct
4 Correct 22 ms 42580 KB Output is correct
5 Correct 21 ms 42580 KB Output is correct
6 Correct 25 ms 42476 KB Output is correct
7 Correct 23 ms 42568 KB Output is correct
8 Correct 22 ms 42580 KB Output is correct
9 Correct 23 ms 42472 KB Output is correct
10 Correct 28 ms 42556 KB Output is correct
11 Correct 26 ms 42604 KB Output is correct
12 Correct 23 ms 42532 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 42592 KB Output is correct
2 Correct 22 ms 42572 KB Output is correct
3 Correct 29 ms 42592 KB Output is correct
4 Correct 22 ms 42580 KB Output is correct
5 Correct 21 ms 42580 KB Output is correct
6 Correct 25 ms 42476 KB Output is correct
7 Correct 23 ms 42568 KB Output is correct
8 Correct 22 ms 42580 KB Output is correct
9 Correct 23 ms 42472 KB Output is correct
10 Correct 28 ms 42556 KB Output is correct
11 Correct 26 ms 42604 KB Output is correct
12 Correct 23 ms 42532 KB Output is correct
13 Correct 26 ms 42580 KB Output is correct
14 Correct 28 ms 42508 KB Output is correct
15 Correct 26 ms 42584 KB Output is correct
16 Correct 23 ms 42552 KB Output is correct
17 Correct 26 ms 42580 KB Output is correct
18 Correct 23 ms 42532 KB Output is correct
19 Correct 26 ms 42616 KB Output is correct
20 Correct 27 ms 42636 KB Output is correct
21 Correct 24 ms 42596 KB Output is correct
22 Correct 24 ms 42616 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 42592 KB Output is correct
2 Correct 22 ms 42572 KB Output is correct
3 Correct 29 ms 42592 KB Output is correct
4 Correct 22 ms 42580 KB Output is correct
5 Correct 21 ms 42580 KB Output is correct
6 Correct 25 ms 42476 KB Output is correct
7 Correct 23 ms 42568 KB Output is correct
8 Correct 22 ms 42580 KB Output is correct
9 Correct 23 ms 42472 KB Output is correct
10 Correct 28 ms 42556 KB Output is correct
11 Correct 26 ms 42604 KB Output is correct
12 Correct 23 ms 42532 KB Output is correct
13 Correct 26 ms 42580 KB Output is correct
14 Correct 28 ms 42508 KB Output is correct
15 Correct 26 ms 42584 KB Output is correct
16 Correct 23 ms 42552 KB Output is correct
17 Correct 26 ms 42580 KB Output is correct
18 Correct 23 ms 42532 KB Output is correct
19 Correct 26 ms 42616 KB Output is correct
20 Correct 27 ms 42636 KB Output is correct
21 Correct 24 ms 42596 KB Output is correct
22 Correct 24 ms 42616 KB Output is correct
23 Correct 34 ms 44116 KB Output is correct
24 Correct 34 ms 44016 KB Output is correct
25 Correct 33 ms 44060 KB Output is correct
26 Correct 46 ms 45524 KB Output is correct
27 Correct 51 ms 45688 KB Output is correct
28 Correct 49 ms 46804 KB Output is correct
29 Correct 45 ms 46600 KB Output is correct
30 Correct 43 ms 46464 KB Output is correct
31 Correct 50 ms 46476 KB Output is correct

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 42592 KB Output is correct
2 Correct 22 ms 42572 KB Output is correct
3 Correct 29 ms 42592 KB Output is correct
4 Correct 22 ms 42580 KB Output is correct
5 Correct 21 ms 42580 KB Output is correct
6 Correct 25 ms 42476 KB Output is correct
7 Correct 23 ms 42568 KB Output is correct
8 Correct 22 ms 42580 KB Output is correct
9 Correct 23 ms 42472 KB Output is correct
10 Correct 28 ms 42556 KB Output is correct
11 Correct 26 ms 42604 KB Output is correct
12 Correct 23 ms 42532 KB Output is correct
13 Correct 26 ms 42580 KB Output is correct
14 Correct 28 ms 42508 KB Output is correct
15 Correct 26 ms 42584 KB Output is correct
16 Correct 23 ms 42552 KB Output is correct
17 Correct 26 ms 42580 KB Output is correct
18 Correct 23 ms 42532 KB Output is correct
19 Correct 26 ms 42616 KB Output is correct
20 Correct 27 ms 42636 KB Output is correct
21 Correct 24 ms 42596 KB Output is correct
22 Correct 24 ms 42616 KB Output is correct
23 Correct 34 ms 44116 KB Output is correct
24 Correct 34 ms 44016 KB Output is correct
25 Correct 33 ms 44060 KB Output is correct
26 Correct 46 ms 45524 KB Output is correct
27 Correct 51 ms 45688 KB Output is correct
28 Correct 49 ms 46804 KB Output is correct
29 Correct 45 ms 46600 KB Output is correct
30 Correct 43 ms 46464 KB Output is correct
31 Correct 50 ms 46476 KB Output is correct
32 Correct 177 ms 57820 KB Output is correct
33 Correct 176 ms 57960 KB Output is correct
34 Correct 190 ms 57916 KB Output is correct
35 Correct 730 ms 103840 KB Output is correct
36 Correct 821 ms 103696 KB Output is correct
37 Correct 751 ms 103628 KB Output is correct
38 Execution timed out 1101 ms 127312 KB Time limit exceeded
39 Halted 0 ms 0 KB -