QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#120636#6538. Lonely KingSortingWA 3ms18736kbC++202.6kb2023-07-07 05:13:172023-07-07 05:13:20

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-07 05:13:20]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:18736kb
  • [2023-07-07 05:13:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};

const int MAXN = 2e5 + 7 ;

int n ;
vector < int > v[ MAXN ] ;
ll a[ MAXN ] ;
ll ans ;

ll lazy[ MAXN ] ;
LineContainer aux[ MAXN ] ;
ll hh[ MAXN ] ;

void dfs ( int x ) {
    int heavy = 0 ;
    ll sm = 0 ;
    for ( auto y : v[ x ] ) {
        dfs ( y ) ;
        if ( aux[ y ].size ( ) > aux[ heavy ].size ( ) ) { heavy = y ; }
        hh[ y ] = aux[ y ].query ( a[ x ] ) + lazy[ y ] ;
        sm += hh[ y ] ;
    }
    if ( x == 1 ) {
        ans = sm ;
        return ;
    }
    if ( heavy == 0 ) {
        aux[ x ].add ( a[ x ] , 0 ) ;
        return ;
    }
    swap ( aux[ x ] , aux[ heavy ] ) ;
    lazy[ x ] = lazy[ heavy ] + sm - hh[ heavy ] ;
    for ( auto y : v[ x ] ) {
        if ( y == heavy ) { continue ; }
        for ( auto e : aux[ y ] ) {
            aux[ x ].add ( e.k , e.m + sm - hh[ y ] + lazy[ y ] - lazy[ x ] ) ;
        }
    }
}

void solve ( ) {
    cin >> n ;
    for ( int i = 2 , prv ; i <= n ; ++ i ) {
        cin >> prv ;
        v[ prv ].push_back ( i ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
    }
    dfs ( 1 ) ;
    cout << ans << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ;
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 18736kb

input:

4
1 1 2
2 1 3 2

output:

10

result:

ok 1 number(s): "10"

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 18604kb

input:

50
1 2 1 1 2 1 6 3 7 5 11 11 8 10 7 8 9 7 17 2 18 4 23 8 17 21 3 19 2 4 21 18 1 26 21 36 26 24 7 7 29 27 19 29 36 11 29 42 21
15 31 15 40 15 33 2 33 15 6 50 48 33 6 43 36 19 37 28 32 47 50 8 26 50 44 50 31 32 44 22 15 46 11 33 38 22 27 43 29 8 1 21 31 28 26 39 29 39 42

output:

26301

result:

wrong answer 1st numbers differ - expected: '22728', found: '26301'