oj.uz

Submission #279768

# Submission time Handle Problem Language Result Execution time Memory
279768 2020-08-22T10:56:09 Z infinite_iq Dynamic Diameter (CEOI19_diameter) C++14
66 / 100
 1329 ms 44508 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]);
        }
  		exit (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 3 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 3 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 2688 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2688 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 3 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 3 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 2688 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2688 KB Output is correct
17 Correct 2 ms 2688 KB Output is correct
18 Correct 2 ms 2688 KB Output is correct
19 Correct 121 ms 2952 KB Output is correct
20 Correct 127 ms 2808 KB Output is correct
21 Correct 137 ms 2816 KB Output is correct
22 Correct 184 ms 2816 KB Output is correct
23 Correct 932 ms 3192 KB Output is correct
24 Correct 1053 ms 3208 KB Output is correct
25 Correct 1069 ms 3404 KB Output is correct
26 Correct 1329 ms 3720 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 4 ms 2688 KB Output is correct
4 Correct 17 ms 2816 KB Output is correct
5 Correct 79 ms 3196 KB Output is correct
6 Incorrect 2 ms 2688 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2816 KB Output is correct
2 Correct 7 ms 2816 KB Output is correct
3 Correct 25 ms 3576 KB Output is correct
4 Correct 56 ms 4216 KB Output is correct
5 Correct 7 ms 3712 KB Output is correct
6 Correct 12 ms 3840 KB Output is correct
7 Correct 39 ms 4472 KB Output is correct
8 Correct 57 ms 5240 KB Output is correct
9 Correct 28 ms 7964 KB Output is correct
10 Correct 33 ms 8168 KB Output is correct
11 Correct 56 ms 8824 KB Output is correct
12 Correct 89 ms 9592 KB Output is correct
13 Correct 52 ms 13304 KB Output is correct
14 Correct 62 ms 13432 KB Output is correct
15 Correct 87 ms 14072 KB Output is correct
16 Correct 119 ms 14968 KB Output is correct
17 Correct 174 ms 14712 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 31608 KB Output is correct
2 Correct 597 ms 31612 KB Output is correct
3 Correct 592 ms 31668 KB Output is correct
4 Correct 590 ms 31864 KB Output is correct
5 Correct 593 ms 32060 KB Output is correct
6 Correct 623 ms 34092 KB Output is correct
7 Correct 624 ms 36344 KB Output is correct
8 Correct 634 ms 36344 KB Output is correct
9 Correct 618 ms 36472 KB Output is correct
10 Correct 664 ms 36600 KB Output is correct
11 Correct 638 ms 36692 KB Output is correct
12 Correct 627 ms 37448 KB Output is correct
13 Correct 581 ms 44000 KB Output is correct
14 Correct 695 ms 44048 KB Output is correct
15 Correct 689 ms 43988 KB Output is correct
16 Correct 654 ms 44024 KB Output is correct
17 Correct 696 ms 43380 KB Output is correct
18 Correct 666 ms 40392 KB Output is correct
19 Correct 650 ms 44508 KB Output is correct
20 Correct 614 ms 44312 KB Output is correct
21 Correct 694 ms 44408 KB Output is correct
22 Correct 688 ms 44280 KB Output is correct
23 Correct 731 ms 43892 KB Output is correct
24 Correct 695 ms 40696 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 3 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 3 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 2688 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2688 KB Output is correct
17 Correct 2 ms 2688 KB Output is correct
18 Correct 2 ms 2688 KB Output is correct
19 Correct 121 ms 2952 KB Output is correct
20 Correct 127 ms 2808 KB Output is correct
21 Correct 137 ms 2816 KB Output is correct
22 Correct 184 ms 2816 KB Output is correct
23 Correct 932 ms 3192 KB Output is correct
24 Correct 1053 ms 3208 KB Output is correct
25 Correct 1069 ms 3404 KB Output is correct
26 Correct 1329 ms 3720 KB Output is correct
27 Correct 2 ms 2688 KB Output is correct
28 Correct 2 ms 2688 KB Output is correct
29 Correct 4 ms 2688 KB Output is correct
30 Correct 17 ms 2816 KB Output is correct
31 Correct 79 ms 3196 KB Output is correct
32 Incorrect 2 ms 2688 KB Output isn't correct
33 Halted 0 ms 0 KB -