oj.uz

Submission #537192

# Submission time Handle Problem Language Result Execution time Memory
537192 2022-03-14T17:38:19 Z NaimSS Beads and wires (APIO14_beads) C++14
100 / 100
 589 ms 69968 KB 
#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
#define sz(v) ((int)v.size())
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
//#define left oooooopss
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll b,ll e,ll m){
  b%=m;
  ll ans = 1;
  for (; e; b = b * b % m, e /= 2)
      if (e & 1) ans = ans * b % m;
  return ans;
}
  
// debug:
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ 
  cerr << ' ' << H; 
  dbg_out(T...); 
}
#ifdef LOCAL
#define dbg(...) cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl
#else
#define dbg(...) 42
#endif
//
const int N = 200100;
vector<pll> g[N];
ll dp[N][2];
int n;
int vis[N][2];
int pai[N];
multiset<ll> MX[N];
ll solve(int v,int pp,int p){
  ll &x = dp[v][pp];
  if(vis[v][pp])return x;
  vis[v][pp]=1;
  pai[v] = p;
  x=0;
  ll sum=0;

  MX[v].insert(-1e9);
  
  for(auto To : g[v])if(To.ff != p){
    ll to = To.ff;
    ll w = To.ss;
    
    if(pp){
      sum += max(solve(to,0,v),solve(to,1,v) + w);  
      MX[v].insert(w - max(solve(to,0,v),solve(to,1,v) + w) + solve(to,0,v));
    }else{
      sum += max(solve(to,0,v),solve(to,1,v) + w);
    }
  }
  if(pp)x = sum + *MX[v].rbegin();
  else x = sum;
  return x;
}

ll mx=0;
void solve2(int v,int p=-1){
  solve(v,0,p);
  solve(v,1,p);
  assert(vis[v][0] && vis[v][1]);
  mx = max(mx,dp[v][0]);
  for(auto To : g[v])if(To.ff!=p){
    ll to = To.ff,w = To.ss;
    //salvar:
    pll cur1 = pll(dp[v][0],dp[v][1]);
    pll cur2 = pll(dp[to][0],dp[to][1]);

    // conserta pai
    dp[v][0]-=max(dp[to][0],dp[to][1] + w);
    dp[v][1]-=max(dp[to][0],dp[to][1] + w);
    dp[v][1]-=*MX[v].rbegin();
    ll valor = w - max(solve(to,0,v),solve(to,1,v) + w) + solve(to,0,v);

    MX[v].erase(MX[v].find(valor));
    dp[v][1] += *MX[v].rbegin();
    // conserta filho:

    dp[to][0] += max(dp[v][0],dp[v][1] + w);
    assert(MX[to].size()>0);
    dp[to][1] -= *MX[to].rbegin();
    ll valor2 = w - max(dp[v][0],dp[v][1] + w) + dp[v][0];
    MX[to].insert(valor2);
    dp[to][1] += max(dp[v][0],dp[v][1] + w) + *MX[to].rbegin();

    solve2(to,v);

    //rollback:
    dp[v][0] = cur1.ff,dp[v][1]=cur1.ss;
    dp[to][0] = cur2.ff,dp[to][1]=cur2.ss;
    MX[v].insert(valor);

    MX[to].erase(MX[to].find(valor2));
  }

}
  
int32_t main(){
    fastio;
    cin >> n;
    ll tot=0;
    rep(i,1,n){
      int a,b,w;
      cin >> a >> b >> w;
      g[a].pb(pll(b,w));
      g[b].pb(pll(a,w));
      tot+=w;
    }
    dbg(tot);
    ms(dp,-1);
    solve(1,0,-1);
    solve(1,1,-1);
    solve2(1);
    cout << mx << endl;

    // math -> gcd it all
    // Did u check N=1? Did you switch N,M?
}

Compilation message

beads.cpp: In function 'int32_t main()':
beads.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
beads.cpp:138:5: note: in expansion of macro 'dbg'
  138 |     dbg(tot);
      |     ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17536 KB Output is correct
2 Correct 11 ms 17492 KB Output is correct
3 Correct 10 ms 17532 KB Output is correct
4 Correct 9 ms 17492 KB Output is correct
5 Correct 9 ms 17564 KB Output is correct
6 Correct 9 ms 17484 KB Output is correct
7 Correct 9 ms 17476 KB Output is correct
8 Correct 9 ms 17492 KB Output is correct
9 Correct 9 ms 17544 KB Output is correct
10 Correct 10 ms 17576 KB Output is correct
11 Correct 10 ms 17492 KB Output is correct
12 Correct 13 ms 17552 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17536 KB Output is correct
2 Correct 11 ms 17492 KB Output is correct
3 Correct 10 ms 17532 KB Output is correct
4 Correct 9 ms 17492 KB Output is correct
5 Correct 9 ms 17564 KB Output is correct
6 Correct 9 ms 17484 KB Output is correct
7 Correct 9 ms 17476 KB Output is correct
8 Correct 9 ms 17492 KB Output is correct
9 Correct 9 ms 17544 KB Output is correct
10 Correct 10 ms 17576 KB Output is correct
11 Correct 10 ms 17492 KB Output is correct
12 Correct 13 ms 17552 KB Output is correct
13 Correct 12 ms 17524 KB Output is correct
14 Correct 9 ms 17492 KB Output is correct
15 Correct 10 ms 17592 KB Output is correct
16 Correct 11 ms 17492 KB Output is correct
17 Correct 10 ms 17492 KB Output is correct
18 Correct 13 ms 17492 KB Output is correct
19 Correct 12 ms 17552 KB Output is correct
20 Correct 10 ms 17500 KB Output is correct
21 Correct 9 ms 17492 KB Output is correct
22 Correct 10 ms 17620 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17536 KB Output is correct
2 Correct 11 ms 17492 KB Output is correct
3 Correct 10 ms 17532 KB Output is correct
4 Correct 9 ms 17492 KB Output is correct
5 Correct 9 ms 17564 KB Output is correct
6 Correct 9 ms 17484 KB Output is correct
7 Correct 9 ms 17476 KB Output is correct
8 Correct 9 ms 17492 KB Output is correct
9 Correct 9 ms 17544 KB Output is correct
10 Correct 10 ms 17576 KB Output is correct
11 Correct 10 ms 17492 KB Output is correct
12 Correct 13 ms 17552 KB Output is correct
13 Correct 12 ms 17524 KB Output is correct
14 Correct 9 ms 17492 KB Output is correct
15 Correct 10 ms 17592 KB Output is correct
16 Correct 11 ms 17492 KB Output is correct
17 Correct 10 ms 17492 KB Output is correct
18 Correct 13 ms 17492 KB Output is correct
19 Correct 12 ms 17552 KB Output is correct
20 Correct 10 ms 17500 KB Output is correct
21 Correct 9 ms 17492 KB Output is correct
22 Correct 10 ms 17620 KB Output is correct
23 Correct 13 ms 18516 KB Output is correct
24 Correct 15 ms 18644 KB Output is correct
25 Correct 18 ms 18584 KB Output is correct
26 Correct 21 ms 19668 KB Output is correct
27 Correct 20 ms 19656 KB Output is correct
28 Correct 22 ms 19696 KB Output is correct
29 Correct 24 ms 19692 KB Output is correct
30 Correct 22 ms 19788 KB Output is correct
31 Correct 20 ms 20424 KB Output is correct

Subtask #4
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17536 KB Output is correct
2 Correct 11 ms 17492 KB Output is correct
3 Correct 10 ms 17532 KB Output is correct
4 Correct 9 ms 17492 KB Output is correct
5 Correct 9 ms 17564 KB Output is correct
6 Correct 9 ms 17484 KB Output is correct
7 Correct 9 ms 17476 KB Output is correct
8 Correct 9 ms 17492 KB Output is correct
9 Correct 9 ms 17544 KB Output is correct
10 Correct 10 ms 17576 KB Output is correct
11 Correct 10 ms 17492 KB Output is correct
12 Correct 13 ms 17552 KB Output is correct
13 Correct 12 ms 17524 KB Output is correct
14 Correct 9 ms 17492 KB Output is correct
15 Correct 10 ms 17592 KB Output is correct
16 Correct 11 ms 17492 KB Output is correct
17 Correct 10 ms 17492 KB Output is correct
18 Correct 13 ms 17492 KB Output is correct
19 Correct 12 ms 17552 KB Output is correct
20 Correct 10 ms 17500 KB Output is correct
21 Correct 9 ms 17492 KB Output is correct
22 Correct 10 ms 17620 KB Output is correct
23 Correct 13 ms 18516 KB Output is correct
24 Correct 15 ms 18644 KB Output is correct
25 Correct 18 ms 18584 KB Output is correct
26 Correct 21 ms 19668 KB Output is correct
27 Correct 20 ms 19656 KB Output is correct
28 Correct 22 ms 19696 KB Output is correct
29 Correct 24 ms 19692 KB Output is correct
30 Correct 22 ms 19788 KB Output is correct
31 Correct 20 ms 20424 KB Output is correct
32 Correct 95 ms 28520 KB Output is correct
33 Correct 89 ms 28476 KB Output is correct
34 Correct 83 ms 28492 KB Output is correct
35 Correct 429 ms 61944 KB Output is correct
36 Correct 487 ms 61856 KB Output is correct
37 Correct 434 ms 61748 KB Output is correct
38 Correct 563 ms 61152 KB Output is correct
39 Correct 588 ms 60980 KB Output is correct
40 Correct 589 ms 61100 KB Output is correct
41 Correct 555 ms 69968 KB Output is correct