oj.uz

Submission #537173

# Submission time Handle Problem Language Result Execution time Memory
537173 2022-03-14T17:16:09 Z NaimSS Beads and wires (APIO14_beads) C++14
13 / 100
 1000 ms 5040 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 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;
  ll v0 = solve(to,0,v);
  ll v1 = solve(to,1,v);
  
  if(pp){
    sum += max(v0,v1 + w);
    mx = max(mx,w - max(v0,v1+ w) + v0);  
  }else{
    sum += max(v0,v1 + w);
  }
}
if(pp)return sum + mx;
else return sum;
}

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);
  
  ll mx=0;
  for(int i=1;i<=n;i++){
  //  ms(dp,-1);
    mx = max(mx,solve(i,0,-1));
    if(mx==tot)break;
  }

  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:89:3: note: in expansion of macro 'dbg'
   89 |   dbg(tot);
      |   ^~~

Subtask #1
13.0 / 13.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 11 ms 4948 KB Output is correct
14 Correct 20 ms 5024 KB Output is correct
15 Correct 9 ms 4948 KB Output is correct
16 Correct 119 ms 5016 KB Output is correct
17 Correct 126 ms 5016 KB Output is correct
18 Correct 506 ms 5020 KB Output is correct
19 Correct 6 ms 4948 KB Output is correct
20 Correct 5 ms 5040 KB Output is correct
21 Correct 4 ms 4948 KB Output is correct
22 Execution timed out 1091 ms 4948 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 11 ms 4948 KB Output is correct
14 Correct 20 ms 5024 KB Output is correct
15 Correct 9 ms 4948 KB Output is correct
16 Correct 119 ms 5016 KB Output is correct
17 Correct 126 ms 5016 KB Output is correct
18 Correct 506 ms 5020 KB Output is correct
19 Correct 6 ms 4948 KB Output is correct
20 Correct 5 ms 5040 KB Output is correct
21 Correct 4 ms 4948 KB Output is correct
22 Execution timed out 1091 ms 4948 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 11 ms 4948 KB Output is correct
14 Correct 20 ms 5024 KB Output is correct
15 Correct 9 ms 4948 KB Output is correct
16 Correct 119 ms 5016 KB Output is correct
17 Correct 126 ms 5016 KB Output is correct
18 Correct 506 ms 5020 KB Output is correct
19 Correct 6 ms 4948 KB Output is correct
20 Correct 5 ms 5040 KB Output is correct
21 Correct 4 ms 4948 KB Output is correct
22 Execution timed out 1091 ms 4948 KB Time limit exceeded
23 Halted 0 ms 0 KB -