Submission #334977

#	Time	Username	Problem	Language	Result	Execution time	Memory
334977		Dymo	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	231 ms	42732 KiB

election_campaign

#include<bits/stdc++.h>
using namespace std;


#define pb    push_back
#define eb   emplace_back
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=1e5+10;
const ll mod =1e9+7 ;
const ll base=3e18;
/// con 15 ngay thoi thang ngu
vector<pair<pll,ll>> adj1[maxn];
vector<ll> adj[maxn];

ll dp[maxn];
ll dep[maxn];
ll anc[maxn][20];

ll cnt=0;

void dfs(ll u,ll par)
{
    anc[u][0]=par;
    for (int i=1;i<=19;i++)
    {
         anc[u][i]=anc[anc[u][i-1]][i-1];
    }
    for (auto to:adj[u])
    {
        if (to==par) continue;
        dep[to]=dep[u]+1;
        dfs(to, u);
    }

}
ll lca(ll x,ll y)
{
    if (dep[x]<dep[y]) swap(x,y);
    ll kc=dep[x]-dep[y];
    for (int i=19;i>=0;i--)
    {
        if (kc&(1ll<<i))
        {
            x=anc[x][i];
        }
    }
    if (x==y) return x;
    for (int i=19;i>=0;i--)
    {
        if (anc[x][i]!=anc[y][i])
        {
            x=anc[x][i];
            y=anc[y][i];
        }
    }
    return anc[x][0];

}
ll f[maxn];
ll pos[maxn];
ll near(ll x,ll y)
{
    ll kc=dep[x]-dep[y]-1;
    for (int i=19;i>=0;i--)
    {
        if (kc&(1ll<<i))
        {
            x=anc[x][i];
        }
    }
    return x;
}
ll dp1[maxn];

void dfs1(ll u,ll par)
{
    dp[u]=0;
    ll cnt=0;
    f[0]=0;
    for (auto to:adj[u])
    {
        if (to==par) continue;
        dfs1(to,u);
        pos[to]=cnt;
        dp[u]+=dp[to];
     //   f[cnt]+=dp[to];
   //    if (u==3) cout <<f[cnt]<<" "<<dp[to]<<" "<<dp[u]<<endl;

    }
      for (auto to:adj[u])
    {
        cnt++;
        f[cnt]=f[cnt-1];
        if (to==par) continue;
        f[cnt]+=dp[to];
   //    if (u==3) cout <<f[cnt]<<" "<<dp[to]<<" "<<dp[u]<<endl;

    }
    dp1[u]=dp[u];
  //  if (u==3) cout <<adj1[u].size()<<" "<<cnt<<" "<<f[cnt]<<endl;
    for (auto p:adj1[u])
    {
       ll x=p.ff.ff;
       ll y=p.ff.ss;
       ll w=p.ss;
       if (dep[x]<dep[y]) swap(x,y);
       if (y==u)
       {

          ll p=near(x,u);
        //  if (u==3) cout <<p<<" "<<dp1[x]<<" "<<f[cnt]<<" "<<w<<" "<<dp[p]<<endl;
          ll ans=f[cnt]-dp[p]+w+dp1[x];
          dp[u]=max(dp[u],ans);
       }
       else
       {
          ll p=near(x,u);
          ll p1=near(y,u);
          ll ans=f[cnt]-dp[p]-dp[p1]+w+dp1[x]+dp1[y];
          dp[u]=max(dp[u],ans);
       }
    }

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("harbingers.in", "r"))
    {
        freopen("harbingers.in", "r", stdin);
        freopen("harbingers.out", "w", stdout);
    }
    ll n;
     cin>> n;
     for (int i=1;i<=n-1;i++)
     {
         ll x, y;
          cin>> x>> y;
          adj[x].pb(y);
          adj[y].pb(x);
     }
     dfs(1,0);
     ll q;
     cin>> q;
     for (int i=1;i<=q;i++)
     {
        ll x, y, w;
         cin>> x>> y>> w;
         adj1[lca(x,y)].pb(make_pair(make_pair(x,y),w));
     }
     dfs1(1,0);
    cout <<dp[1];




}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  136 |         freopen("harbingers.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  137 |         freopen("harbingers.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40