Submission #335004

#	Time	Username	Problem	Language	Result	Execution time	Memory
335004		Dymo	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	319 ms	43500 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;
ll f[maxn];
ll l[maxn];
ll fwt[2*maxn];
void update(ll l, ll r, ll d) {
    for (int p = l; p <= cnt; p += p & -p) fwt[p] = (fwt[p] + d) % mod;
    ++r;
    for (int p = r; p <= cnt; p += p & -p) fwt[p] = (fwt[p] + mod - d) % mod;
}
ll get(ll p) {
    ll ret = 0;
    for (; p; p -= p & -p) ret = (ret + fwt[p]) % mod;
    return ret;
}

void dfs(ll u,ll par)
{
    cnt++;
    f[u]=cnt;
    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);
    }
    l[u]=cnt;

}
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 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;

    for (auto to:adj[u])
    {
        if (to==par) continue;
        dfs1(to,u);
        update(f[u],l[u],dp[to]);
        update(f[to],l[to],-dp[to]);
        dp[u]+=dp[to];
    }
  //  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;
       dp[u]=max(dp[u],get(f[x])+get(f[y])-get(f[par])-get(f[u])+w);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.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];
/*7
2 1
3 2
4 1
5 2
6 3
7 5
3
3 6 4
2 3 5
4 7 7
*/



}

Compilation message (stderr)

election_campaign.cpp: In function 'void dfs1(long long int, long long int)':
election_campaign.cpp:98:8: warning: unused variable 'cnt' [-Wunused-variable]
   98 |     ll cnt=0;
      |        ^~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  124 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  125 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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