oj.uz

Submission #537168

# Submission time Handle Problem Language Result Execution time Memory
537168 2022-03-14T17:12:15 Z NaimSS Beads and wires (APIO14_beads) C++14
28 / 100
 129 ms 8452 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;

ll solve(int v,int pp,int p){
  ll &x = dp[v][pp];
  if(x!=-1)return x;
  x=0;
  ll sum=0;
  ll mx = (pp == 1 ? -1e9 : 0);
  for(auto To : g[v])if(To.ff != p){
    int to = To.ff;
    int w = To.ss;
    
    if(pp){
      sum += max(solve(to,0,v),solve(to,1,v) + w);
      mx = max(mx,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;
  else x = sum;
  return x;
}

int32_t main(){
    fastio;
    ms(dp,-1);
    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);
    vector<int> v;
    rep(i,1,n+1)v.pb(i);
    shuffle(all(v),rng);
    ll mx=0;
    rep(i,0,min(400,n)){
      ms(dp,-1);
      mx = max(mx,solve(v[i],0,-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:92:5: note: in expansion of macro 'dbg'
   92 |     dbg(tot);
      |     ^~~

Subtask #1
13.0 / 13.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 7 ms 8048 KB Output is correct
3 Correct 5 ms 8164 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 5 ms 8148 KB Output is correct
6 Correct 5 ms 8148 KB Output is correct
7 Correct 5 ms 8148 KB Output is correct
8 Correct 7 ms 8148 KB Output is correct
9 Correct 5 ms 8148 KB Output is correct
10 Correct 7 ms 8148 KB Output is correct
11 Correct 6 ms 8148 KB Output is correct
12 Correct 5 ms 8148 KB Output is correct
13 Correct 12 ms 8164 KB Output is correct
14 Correct 12 ms 8160 KB Output is correct
15 Correct 11 ms 8148 KB Output is correct
16 Correct 24 ms 8148 KB Output is correct
17 Correct 21 ms 8168 KB Output is correct
18 Correct 22 ms 8148 KB Output is correct
19 Correct 30 ms 8148 KB Output is correct
20 Correct 21 ms 8172 KB Output is correct
21 Correct 25 ms 8164 KB Output is correct
22 Correct 22 ms 8164 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 7 ms 8048 KB Output is correct
3 Correct 5 ms 8164 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 5 ms 8148 KB Output is correct
6 Correct 5 ms 8148 KB Output is correct
7 Correct 5 ms 8148 KB Output is correct
8 Correct 7 ms 8148 KB Output is correct
9 Correct 5 ms 8148 KB Output is correct
10 Correct 7 ms 8148 KB Output is correct
11 Correct 6 ms 8148 KB Output is correct
12 Correct 5 ms 8148 KB Output is correct
13 Correct 12 ms 8164 KB Output is correct
14 Correct 12 ms 8160 KB Output is correct
15 Correct 11 ms 8148 KB Output is correct
16 Correct 24 ms 8148 KB Output is correct
17 Correct 21 ms 8168 KB Output is correct
18 Correct 22 ms 8148 KB Output is correct
19 Correct 30 ms 8148 KB Output is correct
20 Correct 21 ms 8172 KB Output is correct
21 Correct 25 ms 8164 KB Output is correct
22 Correct 22 ms 8164 KB Output is correct
23 Incorrect 129 ms 8452 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 7 ms 8048 KB Output is correct
3 Correct 5 ms 8164 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 5 ms 8148 KB Output is correct
6 Correct 5 ms 8148 KB Output is correct
7 Correct 5 ms 8148 KB Output is correct
8 Correct 7 ms 8148 KB Output is correct
9 Correct 5 ms 8148 KB Output is correct
10 Correct 7 ms 8148 KB Output is correct
11 Correct 6 ms 8148 KB Output is correct
12 Correct 5 ms 8148 KB Output is correct
13 Correct 12 ms 8164 KB Output is correct
14 Correct 12 ms 8160 KB Output is correct
15 Correct 11 ms 8148 KB Output is correct
16 Correct 24 ms 8148 KB Output is correct
17 Correct 21 ms 8168 KB Output is correct
18 Correct 22 ms 8148 KB Output is correct
19 Correct 30 ms 8148 KB Output is correct
20 Correct 21 ms 8172 KB Output is correct
21 Correct 25 ms 8164 KB Output is correct
22 Correct 22 ms 8164 KB Output is correct
23 Incorrect 129 ms 8452 KB Output isn't correct
24 Halted 0 ms 0 KB -