oj.uz

Submission #551746

# Submission time Handle Problem Language Result Execution time Memory
551746 2022-04-21T12:13:06 Z kwongweng Beads and wires (APIO14_beads) C++17
28 / 100
 1000 ms 852 KB 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
 
ll MOD = 1000000007;
 
ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
ll inverse(ll n){
	return power(n, MOD-2);
}
 
ll add(ll a, ll b){
	return (a+b) % MOD;
}
 
ll mul(ll a, ll b){
	a %= MOD;
	return (a*b) % MOD;
}
 
ll gcd(ll a, ll b){
    if (a == 1) return 1;
    if (a == 0) return b;
    return gcd(b%a, a);
}
 
const int N = 10001;
vii g[N];
int dp[N][4];
//dp[i][0] without edge i, with parent of i
//dp[i][1] with the edge
//dp[i][2-3] from below, 
 
void dfs(int u, int p, int W){
    dp[u][0]=0;dp[u][1]=0;dp[u][2]=0;dp[u][3]=0;
    vii incre_up, incre_down;
    for (ii edge : g[u]){
        int v=edge.fi; int w=edge.se;
        if (v==p) continue;
        dfs(v,u,w);
        dp[u][0]+=max(dp[v][0],dp[v][1]);
        incre_up.pb({dp[v][0]+w-dp[v][1],v});
        incre_down.pb({dp[v][2]+w-dp[v][3]+max(dp[v][2],dp[v][3])-max(dp[v][0],dp[v][1]),v});
    }
    sort(incre_up.rbegin(),incre_up.rend());
    sort(incre_down.rbegin(),incre_down.rend());
    int sz=incre_up.size();
    if (sz>0) dp[u][1]=max(dp[u][0],dp[u][0]+incre_up[0].fi+W);
    if (sz>1){
        if (incre_up[0].se!=incre_down[0].se){
            dp[u][2]=dp[u][0]+incre_up[0].fi+incre_down[0].fi;
        }else{
            dp[u][2]=dp[u][0]+max(incre_up[1].fi+incre_down[0].fi,incre_up[0].fi+incre_down[1].fi);
        }
    }
    if (sz>0){
        dp[u][3]=max(dp[u][2],dp[u][0]+incre_down[0].fi+W);
    }
    //cout<<u<<" ";
    //FOR(i,0,4) cout<<dp[u][i]<<" ";
    //cout<<'\n';
    //if (mini!=MOD) dp[u][1]=max(dp[u][0],dp[u][0]-mini+W);
}
void solve(){
    int n; cin >> n;
    FOR(i,0,n-1){
        int u,v,w; cin>>u>>v>>w;
        g[u].pb({v,w}); g[v].pb({u,w});
    }
    int ans=0;
    FOR(i,1,n+1){
        dfs(i,0,-MOD);
        ans=max({ans,dp[i][0],dp[i][1],dp[i][2],dp[i][3]});
    }
    cout<<ans<<'\n';
    //dfs(1,0,-MOD);
    //cout<<max({dp[1][0],dp[1][1],dp[1][2],dp[1][3]});
    return;
}
 
int main() {
    ios::sync_with_stdio(false);
    int TC = 1;
    //cin >> TC;
    FOR(i, 1, TC+1){
        //cout << "Case #" << i << ": ";
        solve();
    }
}

Compilation message

beads.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("Ofast")
      | 
beads.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 1 ms 564 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 564 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 1 ms 564 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 564 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 2 ms 560 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 5 ms 468 KB Output is correct
17 Correct 5 ms 564 KB Output is correct
18 Correct 5 ms 468 KB Output is correct
19 Correct 5 ms 560 KB Output is correct
20 Correct 4 ms 468 KB Output is correct
21 Correct 4 ms 468 KB Output is correct
22 Correct 4 ms 468 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 1 ms 564 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 564 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 2 ms 560 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 5 ms 468 KB Output is correct
17 Correct 5 ms 564 KB Output is correct
18 Correct 5 ms 468 KB Output is correct
19 Correct 5 ms 560 KB Output is correct
20 Correct 4 ms 468 KB Output is correct
21 Correct 4 ms 468 KB Output is correct
22 Correct 4 ms 468 KB Output is correct
23 Execution timed out 1087 ms 852 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 1 ms 564 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 564 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 2 ms 560 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 5 ms 468 KB Output is correct
17 Correct 5 ms 564 KB Output is correct
18 Correct 5 ms 468 KB Output is correct
19 Correct 5 ms 560 KB Output is correct
20 Correct 4 ms 468 KB Output is correct
21 Correct 4 ms 468 KB Output is correct
22 Correct 4 ms 468 KB Output is correct
23 Execution timed out 1087 ms 852 KB Time limit exceeded
24 Halted 0 ms 0 KB -