oj.uz

답안 #537777

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537777 2022-03-15T13:40:14 Z Lobo 구슬과 끈 (APIO14_beads) C++17
57 / 100
 352 ms 131072 KB 
#include<bits/stdc++.h>
using namespace std;
 
const long long inf = (long long) 1e15 + 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, a[maxn], b[maxn], c[maxn];
vector<int> dp[maxn][4][2], mark[maxn][4][2];
vector<pair<int,int>> g[maxn];

/*
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(mark[u][p][f][id]) return dp[u][p][f][id];
    mark[u][p][f][id] = 1;

    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);

        int ans = -inf;

        //se o outro azul é v
        ans = max(ans, w + sol(v,2,0,0,u) + sol(u,1,f,id+1,ant));
        ans = max(ans, 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
        ans = max(ans, max(sol(v,1,0,0,u),w+sol(v,3,0,0,u)) + sol(u,0,f,id+1,ant));
        ans = max(ans, 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 << " = " << " = " << ans << endl;
        return dp[u][p][f][id] = ans;
    }
    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);

        int ans = -inf;

        //se o outro azul é v
        ans = max(ans, w + sol(v,1,0,0,u) + sol(u,1,f,id+1,ant));
        ans = max(ans, 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
        ans = max(ans, max(sol(v,1,0,0,u),w+sol(v,3,0,0,u)) + sol(u,3,f,id+1,ant));
        ans = max(ans, 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 << " = " << " = " << ans << endl;
        return dp[u][p][f][id] = ans;
    }
    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);

        int ans = -inf;

        //só passa para o próximo podendo ligar para ele com azul 
        //(e o outro azul que vai estar ocupado) ou red
        ans = max(ans, max(sol(v,1,0,0,u),w+sol(v,3,0,0,u)) + sol(u,1,f,id+1,ant));
        ans = max(ans, 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 << " = " << ans << endl;
        return dp[u][p][f][id] = ans;
    }
    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);

        int ans = -inf;

        //só passa para o próximo podendo ligar para ele com azul 
        //(e o outro azul que vai estar ocupado) ou red
        ans = max(ans, max(sol(v,1,0,0,u),w+sol(v,3,0,0,u)) + sol(u,2,f,id+1,ant));
        ans = max(ans, 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
        ans = max(ans, w+sol(v,0,0,0,u) + sol(u,1,f,id+1,ant));
        ans = max(ans, w+sol(v,0,f,0,u) + sol(u,1,0,id+1,ant));

        //liga para o proximo com um uma aresta red
        ans = max(ans, sol(v,2,0,0,u) + sol(u,1,f,id+1,ant));
        ans = max(ans, sol(v,2,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
        ans = max(ans, w+sol(v,1,0,0,u) + sol(u,0,f,id+1,ant));
        ans = max(ans, 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
        ans = max(ans, w+sol(v,2,0,0,u) + sol(u,3,f,id+1,ant));
        ans = max(ans, 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 << " = " << ans << endl;
        return dp[u][p][f][id] = ans;
    }
    return 0;
}
 
void solve() {
    cin >> n;
 
    for(int i = 1; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i];
        g[a[i]].pb(mp(b[i],c[i]));
        g[b[i]].pb(mp(a[i],c[i]));
    }
 
    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(0);
                dp[i][k][1].pb(0);
                mark[i][k][0].pb(0);
                mark[i][k][1].pb(0);
            }
        }
    }
 
 
    cout << sol(rt,2,1,0,0) << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
 
    int tt = 1;
    // cin >> tt;
    while(tt--) solve();
 
}

Compilation message

beads.cpp: In function 'long long int sol(long long int, long long int, long long int, long long int, long long int)':
beads.cpp:43:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         if(id == g[u].size()) return dp[u][p][f][id] = -inf;
      |            ~~~^~~~~~~~~~~~~~
beads.cpp:66:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if(id == g[u].size()) return dp[u][p][f][id] = -inf;
      |            ~~~^~~~~~~~~~~~~~
beads.cpp:89:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         if(id == g[u].size()) {
      |            ~~~^~~~~~~~~~~~~~
beads.cpp:110:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         if(id == g[u].size()) {
      |            ~~~^~~~~~~~~~~~~~
beads.cpp: In function 'void solve()':
beads.cpp:165:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         for(int j = 0; j <= g[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~
beads.cpp:176:27: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  176 |     cout << sol(rt,2,1,0,0) << endl;
      |                           ^

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 80168 KB Output is correct
2 Correct 48 ms 80108 KB Output is correct
3 Correct 40 ms 80128 KB Output is correct
4 Correct 39 ms 80208 KB Output is correct
5 Correct 40 ms 80104 KB Output is correct
6 Correct 39 ms 80076 KB Output is correct
7 Correct 39 ms 80136 KB Output is correct
8 Correct 42 ms 80172 KB Output is correct
9 Correct 42 ms 80124 KB Output is correct
10 Correct 40 ms 80120 KB Output is correct
11 Correct 45 ms 80072 KB Output is correct
12 Correct 37 ms 80184 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 80168 KB Output is correct
2 Correct 48 ms 80108 KB Output is correct
3 Correct 40 ms 80128 KB Output is correct
4 Correct 39 ms 80208 KB Output is correct
5 Correct 40 ms 80104 KB Output is correct
6 Correct 39 ms 80076 KB Output is correct
7 Correct 39 ms 80136 KB Output is correct
8 Correct 42 ms 80172 KB Output is correct
9 Correct 42 ms 80124 KB Output is correct
10 Correct 40 ms 80120 KB Output is correct
11 Correct 45 ms 80072 KB Output is correct
12 Correct 37 ms 80184 KB Output is correct
13 Correct 42 ms 80124 KB Output is correct
14 Correct 37 ms 80204 KB Output is correct
15 Correct 41 ms 80256 KB Output is correct
16 Correct 39 ms 80232 KB Output is correct
17 Correct 40 ms 80292 KB Output is correct
18 Correct 42 ms 80212 KB Output is correct
19 Correct 40 ms 80332 KB Output is correct
20 Correct 39 ms 80344 KB Output is correct
21 Correct 40 ms 80252 KB Output is correct
22 Correct 39 ms 80276 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 80168 KB Output is correct
2 Correct 48 ms 80108 KB Output is correct
3 Correct 40 ms 80128 KB Output is correct
4 Correct 39 ms 80208 KB Output is correct
5 Correct 40 ms 80104 KB Output is correct
6 Correct 39 ms 80076 KB Output is correct
7 Correct 39 ms 80136 KB Output is correct
8 Correct 42 ms 80172 KB Output is correct
9 Correct 42 ms 80124 KB Output is correct
10 Correct 40 ms 80120 KB Output is correct
11 Correct 45 ms 80072 KB Output is correct
12 Correct 37 ms 80184 KB Output is correct
13 Correct 42 ms 80124 KB Output is correct
14 Correct 37 ms 80204 KB Output is correct
15 Correct 41 ms 80256 KB Output is correct
16 Correct 39 ms 80232 KB Output is correct
17 Correct 40 ms 80292 KB Output is correct
18 Correct 42 ms 80212 KB Output is correct
19 Correct 40 ms 80332 KB Output is correct
20 Correct 39 ms 80344 KB Output is correct
21 Correct 40 ms 80252 KB Output is correct
22 Correct 39 ms 80276 KB Output is correct
23 Correct 54 ms 84044 KB Output is correct
24 Correct 56 ms 83916 KB Output is correct
25 Correct 63 ms 83916 KB Output is correct
26 Correct 104 ms 87900 KB Output is correct
27 Correct 95 ms 87908 KB Output is correct
28 Correct 85 ms 88816 KB Output is correct
29 Correct 77 ms 88164 KB Output is correct
30 Correct 86 ms 88268 KB Output is correct
31 Correct 95 ms 88576 KB Output is correct

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 80168 KB Output is correct
2 Correct 48 ms 80108 KB Output is correct
3 Correct 40 ms 80128 KB Output is correct
4 Correct 39 ms 80208 KB Output is correct
5 Correct 40 ms 80104 KB Output is correct
6 Correct 39 ms 80076 KB Output is correct
7 Correct 39 ms 80136 KB Output is correct
8 Correct 42 ms 80172 KB Output is correct
9 Correct 42 ms 80124 KB Output is correct
10 Correct 40 ms 80120 KB Output is correct
11 Correct 45 ms 80072 KB Output is correct
12 Correct 37 ms 80184 KB Output is correct
13 Correct 42 ms 80124 KB Output is correct
14 Correct 37 ms 80204 KB Output is correct
15 Correct 41 ms 80256 KB Output is correct
16 Correct 39 ms 80232 KB Output is correct
17 Correct 40 ms 80292 KB Output is correct
18 Correct 42 ms 80212 KB Output is correct
19 Correct 40 ms 80332 KB Output is correct
20 Correct 39 ms 80344 KB Output is correct
21 Correct 40 ms 80252 KB Output is correct
22 Correct 39 ms 80276 KB Output is correct
23 Correct 54 ms 84044 KB Output is correct
24 Correct 56 ms 83916 KB Output is correct
25 Correct 63 ms 83916 KB Output is correct
26 Correct 104 ms 87900 KB Output is correct
27 Correct 95 ms 87908 KB Output is correct
28 Correct 85 ms 88816 KB Output is correct
29 Correct 77 ms 88164 KB Output is correct
30 Correct 86 ms 88268 KB Output is correct
31 Correct 95 ms 88576 KB Output is correct
32 Correct 275 ms 119628 KB Output is correct
33 Correct 352 ms 119552 KB Output is correct
34 Correct 298 ms 119644 KB Output is correct
35 Runtime error 220 ms 131072 KB Execution killed with signal 9
36 Halted 0 ms 0 KB -