Submission #42082

#	Time	Username	Problem	Language	Result	Execution time	Memory
42082		OneSubmissionMan	Beads and wires (APIO14_beads)	C++11	0 / 100	49 ms	52600 KiB

beads

# include <bits/stdc++.h>

# define F first
# define S second
# define mp make_pair
// everything go according to my plan
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1    Y_U_NO_y1
# define left  Y_U_NO_left
# define right Y_U_NO_right

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;
typedef long double ld;

const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 1110111;
// a pinch of soul
inline void Read_rap () {
  ios_base :: sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}
inline void randomizer3000 () {
  unsigned int seed;
  asm ("rdtsc" : "=A"(seed));
  srand (seed);
}
void files (string problem) {
  if (fopen ((problem + ".in").c_str(),"r")) {
    freopen ((problem + ".in").c_str(),"r",stdin);
    freopen ((problem + ".out").c_str(),"w",stdout);
  }
}
void localInput (string in = "s") {
  if (fopen (in.c_str(), "r"))
    freopen (in.c_str(), "r", stdin);
  else {
    cerr << "Input file not found" << endl;
  }
}          
ll dp[Sz][4];

int n;

vec<int> g[Sz], w[Sz];

void dfs (int v, int pr) {
  for (int to : g[v]) {
    if (to != pr) 
      dfs (to, v);
  }      
  dp[v][0] = 0;
  dp[v][1] = -MX;
  dp[v][2] = -MX;
  for (int to : g[v]) {
    if (to != pr) { 
      dp[v][0] += dp[to][3];
    }
  }     
  ll up = -MX;    
  for (int i = 0; i < sz(g[v]); i++) {
    int to = g[v][i];
    if (to == pr) {
      up = w[v][i];
      break;
    }
  }   
  for (int i = 0; i < sz(g[v]); i++) {
    int to = g[v][i];
    int len = w[v][i];
    if (to != pr) { 
      dp[v][1] = max (dp[v][1], up + max (dp[to][0], dp[to][2]) - dp[to][3] + len + dp[v][0]);
    }
  }
  ll mx[3];
  mx[0] = mx[2] = -MX;
  for (int i = 0; i < sz(g[v]); i++) {
    int to = g[v][i];
    int len = w[v][i];      
    if (to != pr) {
      dp[v][2] = max (dp[v][2], max (dp[to][0] + max (mx[0], mx[2]), dp[to][2] + mx[0]) + len - dp[to][3] + dp[v][0]);
      mx[0] = max (mx[0], dp[to][0] + len - dp[to][3]);
      mx[2] = max (mx[2], dp[to][2] + len - dp[to][3]);
    }
  }
  for (int i = 0; i < 3; i++)
    dp[v][3] = max (dp[v][i], dp[v][3]); 
}       
int main()
{
  Read_rap();
  //localInput();
  cin >> n;        
  for (int i = 1; i < n; i++) {
    int x, y, z; cin >> x >> y >> z;
    g[x].pb (y);
    w[x].pb (z);
    g[y].pb (x);
    w[y].pb (z);
  }
  dfs (1, 1);
  ll mx = 0;     
  for (int i = 0; i < 3; i++) {  
    if (i == 1)
      continue;
    mx = max (mx, dp[1][i]);
  }
  cout << mx;

  return 0;
}










// Coded by Z..

Compilation message (stderr)

beads.cpp: In function 'void files(std::__cxx11::string)':
beads.cpp:37:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen ((problem + ".in").c_str(),"r",stdin);
     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
beads.cpp:38:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen ((problem + ".out").c_str(),"w",stdout);
     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
beads.cpp: In function 'void localInput(std::__cxx11::string)':
beads.cpp:43:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen (in.c_str(), "r", stdin);
     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43