Submission #334977

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
334977	2020-12-10T16:28:09 Z	Dymo	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	231 ms	42732 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5100 KB	Output is correct
2	Correct	4 ms	5100 KB	Output is correct
3	Incorrect	4 ms	5100 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5100 KB	Output is correct
2	Correct	4 ms	5228 KB	Output is correct
3	Correct	6 ms	5356 KB	Output is correct
4	Correct	202 ms	42476 KB	Output is correct
5	Correct	193 ms	42348 KB	Output is correct
6	Correct	159 ms	42348 KB	Output is correct
7	Correct	195 ms	42476 KB	Output is correct
8	Correct	190 ms	42348 KB	Output is correct
9	Correct	179 ms	42476 KB	Output is correct
10	Correct	203 ms	42348 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5100 KB	Output is correct
2	Correct	4 ms	5228 KB	Output is correct
3	Correct	6 ms	5356 KB	Output is correct
4	Correct	202 ms	42476 KB	Output is correct
5	Correct	193 ms	42348 KB	Output is correct
6	Correct	159 ms	42348 KB	Output is correct
7	Correct	195 ms	42476 KB	Output is correct
8	Correct	190 ms	42348 KB	Output is correct
9	Correct	179 ms	42476 KB	Output is correct
10	Correct	203 ms	42348 KB	Output is correct
11	Correct	15 ms	6636 KB	Output is correct
12	Correct	223 ms	42604 KB	Output is correct
13	Correct	211 ms	42604 KB	Output is correct
14	Correct	172 ms	42732 KB	Output is correct
15	Correct	218 ms	42732 KB	Output is correct
16	Correct	169 ms	42680 KB	Output is correct
17	Correct	231 ms	42684 KB	Output is correct
18	Correct	210 ms	42648 KB	Output is correct
19	Correct	174 ms	42732 KB	Output is correct
20	Correct	223 ms	42604 KB	Output is correct