| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 147175 | CaroLinda | Race (IOI11_race) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "race.h"
#define lp(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define pii pair<int,int>
#define ff first
#define ss second
#define mk make_pair
#define pb push_back
#define sz size()
#define mip map<ll,int>::iterator
const int MAXN = 2e5+10 ;
using namespace std ;
int curTime ;
int fatSomaVal[MAXN] ;
int ini[MAXN] , fim[MAXN] , bit[MAXN] , qual[MAXN] , pai[MAXN] , resp[MAXN] ;
ll fatSomaKey[MAXN] , specialEdge[MAXN] ;
vector<pair<int,ll> > adj[MAXN] ;
map<ll , int > mapa[MAXN] ;
bool marc[MAXN];
void add(int x) { for(int i = x ; i < MAXN ; i+=(i&-i)) bit[i] ++ ; }
int qry(int x)
{
int tot = 0 ;
for(int i = x ; i > 0 ; i -= (i&-i))
tot += bit[i] ;
return tot ;
}
ll realKey(int i , ll x) { return x + fatSomaKey[i] + specialEdge[i] ; }
int realVal(int i , ll x) { return mapa[qual[i]][x] + fatSomaVal[i] ; }
void dfs(int x)
{
ini[x] = ++curTime ;
for(pii i : adj[x])
if(ini[i.ff] == 0)
{
dfs(i.ff) ;
pai[i.ff] = x;
specialEdge[i.ff] = i.ss ;
}
fim[x] = curTime ;
}
void printMap(int idx)
{
for(mip it = mapa[idx].begin() ; it != mapa[idx].end() ; it++ )
printf("%lld %d\n" , it->ff, it->ss) ;
printf("\n") ;
}
ll best_path(int N , int K , int H[][2] , ll L[])
{
memset(resp, -1, sizeof resp) ;
lp(i,0,N-1)
{
int a = H[i][0] , b = H[i][1] ;
adj[a].pb(mk(b , L[i])) ;
adj[b].pb(mk(a,L[i])) ;
}
dfs(0) ;
queue<int> q ;
lp(i,0,N)
if(ini[i] == fim[i])
{
q.push(i) ;
marc[i] = true ;
qual[i] = q.sz ;
mapa[q.sz].insert(mk(0,0)) ;
}
while( !q.empty() )
{
int davez = q.front() ;
q.pop() ;
marc[davez] = true ;
add(ini[davez]) ;
if( !marc[pai[davez]] && (qry(fim[pai[davez]]) - qry(ini[pai[davez]])) == (fim[pai[davez]]-ini[pai[davez]]) )
{
marc[pai[davez]] = true ;
q.push(pai[davez]) ;
}
if( ini[davez] == fim[davez] ) continue ;
pii bigChild = mk( mapa[qual[adj[davez][0].ff]].sz , 0 ) ;
for(pii p : adj[davez])
bigChild = max( bigChild , pii( 1*mapa[qual[p.ff]].sz , p.ff ) ) ;
fatSomaKey[davez] = fatSomaKey[ bigChild.ss ] + specialEdge[bigChild.ss] ;
fatSomaVal[davez] = fatSomaVal[bigChild.ss] + 1 ;
qual[davez] = qual[bigChild.ss] ;
if( mapa[qual[davez]].find( K - fatSomaKey[davez] ) != mapa[qual[davez]].end() )
resp[davez] = mapa[qual[davez]][K-fatSomaKey[davez]] + fatSomaVal[davez] ;
lp(i,0,adj[davez].size())
{
int cur = adj[davez][i].ff ;
if(cur == bigChild.ss) continue ;
for(mip it = mapa[qual[cur]].begin() ; it != mapa[qual[cur]].end() ; it++ )
{
ll realX = realKey(cur , it->ff) ;
int realY = realVal(cur , it->ff) + 1 ;
ll vaiUpdtarX = realX - fatSomaKey[davez] ;
int vaiUpdtarY = realY - fatSomaVal[davez] ;
if( K == realX ) resp[davez] = max(resp[davez] , realY) ;
if( mapa[qual[davez]].find( K - vaiUpdtarX ) == mapa[qual[davez]].end() ) continue ;
resp[davez] = max(resp[davez], mapa[qual[davez]][K-vaiUpdtarX] + fatSomaVal[davez] + realY ) ;
}
for(mip it = mapa[qual[cur]].begin() ; it != mapa[qual[cur]].end() ; it++ )
{
ll realX = realKey(cur , it->ff) ;
int realY = realVal(cur , it->ff) + 1 ;
ll vaiUpdtarX = realX - fatSomaKey[davez] ;
int vaiUpdtarY = realY - fatSomaVal[davez] ;
if( mapa[qual[davez]].find(vaiUpdtarX) == mapa[qual[davez]].end() )
mapa[qual[davez]].insert(mk( vaiUpdtarX , vaiUpdtarY )) ;
mapa[qual[davez]][vaiUpdtarX] = max( mapa[qual[davez]][vaiUpdtarX] , vaiUpdtarY ) ;
}
}
}
return *max_element(resp,resp+N) ;
}