oj.uz

Submission #434856

# Submission time Handle Problem Language Result Execution time Memory
434856 2021-06-22T02:34:21 Z cpp219 Beads and wires (APIO14_beads) C++14
28 / 100
 1000 ms 5580 KB 
#pragma GCC optimization O2
#pragma GCC optimization "unroll-loop"
#pragma target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 2e5 + 9;
const ll inf = 1e9 + 7;
vector<LL> g[N];
ll n,x,y,w,dp[N][2],All[N],ans;

void DFS(ll u,ll p){
    ll child = 0;
    for (auto i : g[u]) if (i.fs != p) DFS(i.fs,u),child++;
    dp[u][0] = dp[u][1] = 0;
    if (!child) dp[u][1] = -inf;
    for (auto i : g[u]){
        ll v = i.fs,cost = i.sc;
        if (v == p) continue;
        dp[u][0] += max(dp[v][1] + cost,dp[v][0]);
        All[u] += dp[v][1];
    }
    for (auto i : g[u]){
        ll v = i.fs,cost = i.sc;
        if (v == p) continue;
        ll now = dp[u][0] - max(dp[v][1] + cost,dp[v][0]) + dp[v][0] + cost;
        dp[u][1] = max(dp[u][1],now);
    }
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n;
    for (ll i = 1;i < n;i++){
        cin>>x>>y>>w;
        g[x].push_back({y,w}); g[y].push_back({x,w});
    }
    for (ll i = 1;i <= n;i++){
        DFS(i,0);
        ans = max(ans,dp[i][0]); //cout<<dp[i][0]; return 0;
    }
    cout<<ans;
}

Compilation message

beads.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization O2
      | 
beads.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
beads.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    3 | #pragma target ("avx2")
      | 
beads.cpp: In function 'int main()':
beads.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 3 ms 4940 KB Output is correct
16 Correct 5 ms 4940 KB Output is correct
17 Correct 4 ms 4932 KB Output is correct
18 Correct 5 ms 4940 KB Output is correct
19 Correct 5 ms 4940 KB Output is correct
20 Correct 4 ms 4940 KB Output is correct
21 Correct 5 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 824 ms 5272 KB Output is correct
24 Correct 847 ms 5324 KB Output is correct
25 Correct 915 ms 5324 KB Output is correct
26 Execution timed out 1088 ms 5580 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 3 ms 4940 KB Output is correct
16 Correct 5 ms 4940 KB Output is correct
17 Correct 4 ms 4932 KB Output is correct
18 Correct 5 ms 4940 KB Output is correct
19 Correct 5 ms 4940 KB Output is correct
20 Correct 4 ms 4940 KB Output is correct
21 Correct 5 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 824 ms 5272 KB Output is correct
24 Correct 847 ms 5324 KB Output is correct
25 Correct 915 ms 5324 KB Output is correct
26 Execution timed out 1088 ms 5580 KB Time limit exceeded
27 Halted 0 ms 0 KB -