oj.uz

답안 #537166

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537166 2022-03-14T17:07:54 Z NaimSS 구슬과 끈 (APIO14_beads) C++14
28 / 100
 1000 ms 8404 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);
    
    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:92:5: note: in expansion of macro 'dbg'
   92 |     dbg(tot);
      |     ^~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 6 ms 8148 KB Output is correct
4 Correct 5 ms 8144 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 6 ms 8168 KB Output is correct
9 Correct 5 ms 8144 KB Output is correct
10 Correct 6 ms 8160 KB Output is correct
11 Correct 5 ms 8164 KB Output is correct
12 Correct 5 ms 8276 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 6 ms 8148 KB Output is correct
4 Correct 5 ms 8144 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 6 ms 8168 KB Output is correct
9 Correct 5 ms 8144 KB Output is correct
10 Correct 6 ms 8160 KB Output is correct
11 Correct 5 ms 8164 KB Output is correct
12 Correct 5 ms 8276 KB Output is correct
13 Correct 12 ms 8168 KB Output is correct
14 Correct 13 ms 8148 KB Output is correct
15 Correct 14 ms 8092 KB Output is correct
16 Correct 20 ms 8148 KB Output is correct
17 Correct 20 ms 8148 KB Output is correct
18 Correct 20 ms 8160 KB Output is correct
19 Correct 19 ms 8176 KB Output is correct
20 Correct 19 ms 8148 KB Output is correct
21 Correct 21 ms 8176 KB Output is correct
22 Correct 22 ms 8164 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 6 ms 8148 KB Output is correct
4 Correct 5 ms 8144 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 6 ms 8168 KB Output is correct
9 Correct 5 ms 8144 KB Output is correct
10 Correct 6 ms 8160 KB Output is correct
11 Correct 5 ms 8164 KB Output is correct
12 Correct 5 ms 8276 KB Output is correct
13 Correct 12 ms 8168 KB Output is correct
14 Correct 13 ms 8148 KB Output is correct
15 Correct 14 ms 8092 KB Output is correct
16 Correct 20 ms 8148 KB Output is correct
17 Correct 20 ms 8148 KB Output is correct
18 Correct 20 ms 8160 KB Output is correct
19 Correct 19 ms 8176 KB Output is correct
20 Correct 19 ms 8148 KB Output is correct
21 Correct 21 ms 8176 KB Output is correct
22 Correct 22 ms 8164 KB Output is correct
23 Execution timed out 1083 ms 8404 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 6 ms 8148 KB Output is correct
4 Correct 5 ms 8144 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 6 ms 8168 KB Output is correct
9 Correct 5 ms 8144 KB Output is correct
10 Correct 6 ms 8160 KB Output is correct
11 Correct 5 ms 8164 KB Output is correct
12 Correct 5 ms 8276 KB Output is correct
13 Correct 12 ms 8168 KB Output is correct
14 Correct 13 ms 8148 KB Output is correct
15 Correct 14 ms 8092 KB Output is correct
16 Correct 20 ms 8148 KB Output is correct
17 Correct 20 ms 8148 KB Output is correct
18 Correct 20 ms 8160 KB Output is correct
19 Correct 19 ms 8176 KB Output is correct
20 Correct 19 ms 8148 KB Output is correct
21 Correct 21 ms 8176 KB Output is correct
22 Correct 22 ms 8164 KB Output is correct
23 Execution timed out 1083 ms 8404 KB Time limit exceeded
24 Halted 0 ms 0 KB -