oj.uz

Submission #279767

# Submission time Handle Problem Language Result Execution time Memory
279767 2020-08-22T10:55:17 Z infinite_iq Dynamic Diameter (CEOI19_diameter) C++14
48 / 100
 5000 ms 44280 KB 
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 340
#define mp make_pair
#define mid (l+r)/2
#define le node * 2 
#define ri node * 2 + 1 
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
#define all(x) x.begin(), x.end()
#define gc getchar_unlocked
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef pair<double,ll>pdi;
const ll inf=1e18;
const ll Mod=1e9+7;
const ld Pi=acos(-1) ;
ll n , q , MX , Last ;
vpll v [100009] ;
pll edges [100009] ;
//
pair < pll , ll >  Query ( ll t ) {
        ll id , cost ;
        scanf ("%lld%lld",&id,&cost) ;
        id   = ( id   + Last ) % ( n - 1 ) ;
        cost = ( cost + Last ) % ( MX    ) ;
        ll a = edges [id] .fi , b = edges [id] .se ;
        if ( t ) {
                for ( auto &u : v [a] ) {
                        if ( u .fi == b ) {
                                u .se = cost ;
                                break ;
                        }
                }
                for ( auto &u : v [b] ) {
                        if ( u .fi == a ) {
                                u .se = cost ;
                                break ;
                        }
                }
        }
        return { { a , b } , cost } ;
}
void input () {
        cin >> n >> q >> MX ;
        for ( int i = 0 ; i < n - 1 ; i ++ ) {
                ll a , b , c ;
                scanf ("%lld%lld%lld", &a , &b , &c ) ;
                a -- , b -- ;
                edges [i] = { a , b } ;
                v [a] .pb ( { b , c } ) ;
                v [b] .pb ( { a , c } ) ;
        }
        if ( n == 2 ) {
                while ( q -- ) {
                        cout << Query ( 0 ) . se << endl ; ;
                }
                exit (0) ;
        }
}
// Sub1_2
pi Far ;
int Sub1_2 () {
        return ( n <= 5009 && q <= 5009 ) ;
}
void Dfs1 ( int node , int p , int Crnt ) {
        Far = max ( Far , { Crnt , node } ) ;
        for ( auto u : v [node] ) {
                if ( u .fi == p ) C ;
                Dfs1 ( u .fi , node , Crnt + u .se ) ;
        }
}
int BruteForce () {
        Far = { 0 , 0 } ;
        Dfs1 ( 0 , 0 , 0 ) ;
        Dfs1 ( Far .se , Far .se , 0 ) ;
        return Far .fi ;
}
void Sol1_2 () {
        while ( q -- ) {
                Query (1) ;
                Last = BruteForce () ;
                printf ("%lld\n",Last) ;
        }
        exit (0) ;
}
// Sub4 
ll Dp [100009] , Mx [100009] , P [100009] ;
int Sub4 () {
        for ( int i = 0 ; i < n - 1 ; i ++ ) {
                ll a = edges [i] .fi , b = edges [i] .se ;
                if ( a > b ) {
                        swap ( edges [i] .fi , edges [i] .se ) ;
                }
                a ++ , b ++ ;
                if ( a * 2 != b && a * 2 + 1 != b ) return 0 ;
        }
        return 1 ;
}
void Fill ( int node , int p ) {
        P [node] = p ;
        for ( auto u : v [node] ) {
                if ( u .fi == p ) C ;
                Fill ( u .fi , node ) ;
                Dp [node] = max ( Dp [node] , Dp [u.fi] ) ;
                Dp [node] = max ( Dp [node] , Mx [u.fi] + u .se + Mx [node] ) ;
                Mx [node] = max ( Mx [node] , Mx [u.fi] + u .se ) ;
        }
        Dp [node] = max ( Dp [node] , Mx [node] ) ;
}
void Up ( int node ) {
        Dp [node] = 0 , Mx [node] = 0 ;
        for ( auto u : v [node] ) {
                if ( u .fi == P [node] ) C ;
                Dp [node] = max ( Dp [node] , Dp [u.fi] ) ;
                Dp [node] = max ( Dp [node] , Mx [u.fi] + u .se + Mx [node] ) ;
                Mx [node] = max ( Mx [node] , Mx [u.fi] + u .se ) ;
        }
        if ( P [node] != node )
                Up ( P  [node] ) ;
}
void Sol4 () {
        Fill ( 0 , 0 ) ;
        while ( q -- ) {
                pair < pll , ll > Ret  = Query (1) ;
                ll a = Ret .fi.fi , b = Ret .fi.se , cost = Ret .se ;
                Up ( a ) ;
                Last =  Dp [0] ;
                printf ("%lld\n",Dp [0]);
        }
}
// Sub3_5
mset < ll > s ;
map < pll , ll > Val ;
ll Ord [100009] , Col [100009] , st [100009] , en [100009] ;
ll tree [400009] , lzy [400009] ;
void lzyUpd ( int node , int l , int r ) {
        tree [node] += lzy [node] ;
        if ( l != r ) {
                lzy [le] += lzy [node] ;
                lzy [ri] += lzy [node] ;
        }
        lzy [node] = 0 ;
}
void upd ( int node , int l , int r , int s , int e , ll val ) {
        lzyUpd ( node , l , r ) ;
        if ( s > r || e < l ) return ;
        if ( s <= l && e >= r ) {
                lzy [node] = val ;
                lzyUpd ( node , l , r ) ;
                return ;
        }
        upd ( le , l , mid , s , e , val ) ;
        upd ( ri , mid +1 , r , s , e , val ) ;
        tree [node] = max ( tree [le] , tree [ri] ) ;
}
ll query ( int node , int l , int r , int s , int e ) {
        lzyUpd ( node , l , r ) ;
        if ( s > r || e < l ) return 0ll ;
        if ( s <= l && e >= r ) return tree [node] ;
        return max ( query ( le , l , mid , s , e ) , query ( ri , mid + 1 , r , s , e ) ) ;
}
int timer = 0 , CrntCol = 0 ;
void Dfs ( int node , int p , ll crnt ) {
        Ord [timer] = node ;
        upd ( 1 , 0 , n -1 , timer , timer , crnt ) ;
        Col [node] = CrntCol ;
        st  [node] = timer ++ ;
        P   [node] = p ;
        for ( auto u : v [node] ) {
                Val [ mp ( u.fi , node ) ] = u .se ;
                if ( u.fi == p ) C ;
                Dfs ( u .fi , node , crnt + u .se ) ;
                CrntCol += ( node == 0 ) ;
        }
        en [node] = timer - 1 ;
}
ll Ans () {
        ll sum = 0 ;
        auto it = -- s.end () ;
        sum += *it ;
        if ( it != s.begin () ) {
                it -- ;
                sum += *it ;
        }
        return sum ;
}
void Sol3_5 () {
        Dfs ( 0 , 0 , 0 ) ;
        for ( auto u : v [0] ) {
                int l = st [u.fi] , r = en [u.fi] ;
                Mx [ Col [u.fi] ] = query ( 1 , 0 , n-1 , l , r ) ;
                s .ins ( Mx [ Col [u.fi] ] ) ;
        }
        for ( int i = 0 ; i < n -1 ; i ++ ) {
                int a = edges [i] .fi , b = edges [i] .se ;
                if ( P [a] == b ) {
                        swap ( edges [i] .fi , edges [i] .se ) ;
                }
        }
        while ( q -- ) {
                pair < pll , ll > Ret = Query (0) ;
                ll a = Ret .fi.fi , b = Ret .fi.se , cost = Ret .se ;
                ll bon = cost - Val [ mp ( a , b ) ] ;
                Val [ mp ( a , b ) ] = cost ;
                ll l = st [b] , r = en [b] ;
                upd ( 1 , 0 , n-1 , l , r , bon ) ;
                ll NODE = v [0][Col[b]] .fi ;
                l = st [NODE] , r = en [NODE] ;
                s .era ( s .find ( Mx [ Col [b] ] ) ) ;
                Mx [ Col [b] ] = query ( 1 , 0 , n -1 , l , r ) ;
                s .ins ( Mx [ Col [b] ] ) ;
                Last = Ans () ;
                printf ("%lld\n",Last) ;
        }
}
int main () {
        input () ;
        if ( Sub1_2 () ) Sol1_2 () ; 
        if ( Sub4   () ) Sol4   () ;
        Sol3_5 () ;
}

Compilation message

diameter.cpp: In function 'void Sol4()':
diameter.cpp:143:37: warning: unused variable 'b' [-Wunused-variable]
  143 |                 ll a = Ret .fi.fi , b = Ret .fi.se , cost = Ret .se ;
      |                                     ^
diameter.cpp:143:54: warning: unused variable 'cost' [-Wunused-variable]
  143 |                 ll a = Ret .fi.fi , b = Ret .fi.se , cost = Ret .se ;
      |                                                      ^~~~
diameter.cpp: In function 'std::pair<std::pair<long long int, long long int>, long long int> Query(ll)':
diameter.cpp:41:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |         scanf ("%lld%lld",&id,&cost) ;
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
diameter.cpp: In function 'void input()':
diameter.cpp:65:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |                 scanf ("%lld%lld%lld", &a , &b , &c ) ;
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2688 KB Output is correct
14 Correct 2 ms 2816 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2816 KB Output is correct
17 Correct 2 ms 2688 KB Output is correct
18 Correct 2 ms 2688 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2688 KB Output is correct
14 Correct 2 ms 2816 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2816 KB Output is correct
17 Correct 2 ms 2688 KB Output is correct
18 Correct 2 ms 2688 KB Output is correct
19 Correct 117 ms 2816 KB Output is correct
20 Correct 125 ms 2816 KB Output is correct
21 Correct 138 ms 2936 KB Output is correct
22 Correct 182 ms 2936 KB Output is correct
23 Correct 881 ms 3576 KB Output is correct
24 Correct 1045 ms 3360 KB Output is correct
25 Correct 1096 ms 3448 KB Output is correct
26 Correct 1398 ms 3704 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 17 ms 2816 KB Output is correct
5 Correct 77 ms 3220 KB Output is correct
6 Incorrect 2 ms 2688 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2816 KB Output is correct
2 Execution timed out 5053 ms 30840 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 31572 KB Output is correct
2 Correct 597 ms 31608 KB Output is correct
3 Correct 596 ms 31608 KB Output is correct
4 Correct 600 ms 31608 KB Output is correct
5 Correct 612 ms 31988 KB Output is correct
6 Correct 615 ms 34028 KB Output is correct
7 Correct 589 ms 36612 KB Output is correct
8 Correct 626 ms 36408 KB Output is correct
9 Correct 621 ms 36472 KB Output is correct
10 Correct 640 ms 36472 KB Output is correct
11 Correct 634 ms 36688 KB Output is correct
12 Correct 656 ms 37484 KB Output is correct
13 Correct 587 ms 44052 KB Output is correct
14 Correct 679 ms 44280 KB Output is correct
15 Correct 709 ms 44128 KB Output is correct
16 Correct 679 ms 44152 KB Output is correct
17 Correct 709 ms 43380 KB Output is correct
18 Correct 662 ms 40172 KB Output is correct
19 Correct 635 ms 44188 KB Output is correct
20 Correct 651 ms 44000 KB Output is correct
21 Correct 675 ms 44000 KB Output is correct
22 Correct 659 ms 43896 KB Output is correct
23 Correct 693 ms 43252 KB Output is correct
24 Correct 649 ms 40296 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2688 KB Output is correct
14 Correct 2 ms 2816 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2816 KB Output is correct
17 Correct 2 ms 2688 KB Output is correct
18 Correct 2 ms 2688 KB Output is correct
19 Correct 117 ms 2816 KB Output is correct
20 Correct 125 ms 2816 KB Output is correct
21 Correct 138 ms 2936 KB Output is correct
22 Correct 182 ms 2936 KB Output is correct
23 Correct 881 ms 3576 KB Output is correct
24 Correct 1045 ms 3360 KB Output is correct
25 Correct 1096 ms 3448 KB Output is correct
26 Correct 1398 ms 3704 KB Output is correct
27 Correct 2 ms 2688 KB Output is correct
28 Correct 2 ms 2688 KB Output is correct
29 Correct 3 ms 2688 KB Output is correct
30 Correct 17 ms 2816 KB Output is correct
31 Correct 77 ms 3220 KB Output is correct
32 Incorrect 2 ms 2688 KB Output isn't correct
33 Halted 0 ms 0 KB -