oj.uz

Submission #279772

# Submission time Handle Problem Language Result Execution time Memory
279772 2020-08-22T10:58:45 Z infinite_iq Dynamic Diameter (CEOI19_diameter) C++14
73 / 100
 1353 ms 44816 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 -- ) {
                  		Last = Query ( 0 ) .se ;
                        printf ("%lld\n",Last) ;
                }
                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:144:37: warning: unused variable 'b' [-Wunused-variable]
  144 |                 ll a = Ret .fi.fi , b = Ret .fi.se , cost = Ret .se ;
      |                                     ^
diameter.cpp:144:54: warning: unused variable 'cost' [-Wunused-variable]
  144 |                 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 2816 KB Output is correct
11 Correct 3 ms 2688 KB Output is correct
12 Correct 3 ms 2688 KB Output is correct
13 Correct 2 ms 2688 KB Output is correct
14 Correct 3 ms 2688 KB Output is correct
15 Correct 3 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 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 2816 KB Output is correct
11 Correct 3 ms 2688 KB Output is correct
12 Correct 3 ms 2688 KB Output is correct
13 Correct 2 ms 2688 KB Output is correct
14 Correct 3 ms 2688 KB Output is correct
15 Correct 3 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 120 ms 2936 KB Output is correct
20 Correct 124 ms 2936 KB Output is correct
21 Correct 138 ms 2816 KB Output is correct
22 Correct 178 ms 2936 KB Output is correct
23 Correct 868 ms 3448 KB Output is correct
24 Correct 1020 ms 3320 KB Output is correct
25 Correct 1118 ms 3632 KB Output is correct
26 Correct 1353 ms 3584 KB Output is correct

Subtask #3
7.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 2944 KB Output is correct
5 Correct 79 ms 3832 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 14 ms 2816 KB Output is correct
10 Correct 25 ms 3200 KB Output is correct
11 Correct 122 ms 4252 KB Output is correct
12 Correct 7 ms 3072 KB Output is correct
13 Correct 14 ms 3072 KB Output is correct
14 Correct 111 ms 3072 KB Output is correct
15 Correct 44 ms 4864 KB Output is correct
16 Correct 180 ms 6008 KB Output is correct
17 Correct 219 ms 36196 KB Output is correct
18 Correct 223 ms 36196 KB Output is correct
19 Correct 243 ms 36196 KB Output is correct
20 Correct 311 ms 36452 KB Output is correct
21 Correct 729 ms 37996 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2816 KB Output is correct
2 Correct 10 ms 2944 KB Output is correct
3 Correct 24 ms 3456 KB Output is correct
4 Correct 46 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 35 ms 4504 KB Output is correct
8 Correct 56 ms 5112 KB Output is correct
9 Correct 28 ms 7928 KB Output is correct
10 Correct 33 ms 8056 KB Output is correct
11 Correct 57 ms 8312 KB Output is correct
12 Correct 92 ms 8568 KB Output is correct
13 Correct 54 ms 12536 KB Output is correct
14 Correct 62 ms 12536 KB Output is correct
15 Correct 88 ms 12792 KB Output is correct
16 Correct 114 ms 13048 KB Output is correct
17 Correct 173 ms 13176 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 32248 KB Output is correct
2 Correct 635 ms 32380 KB Output is correct
3 Correct 578 ms 32376 KB Output is correct
4 Correct 576 ms 32376 KB Output is correct
5 Correct 610 ms 32756 KB Output is correct
6 Correct 596 ms 34716 KB Output is correct
7 Correct 586 ms 37112 KB Output is correct
8 Correct 643 ms 37172 KB Output is correct
9 Correct 639 ms 37112 KB Output is correct
10 Correct 624 ms 37112 KB Output is correct
11 Correct 644 ms 37364 KB Output is correct
12 Correct 688 ms 38252 KB Output is correct
13 Correct 620 ms 44768 KB Output is correct
14 Correct 667 ms 44792 KB Output is correct
15 Correct 637 ms 44668 KB Output is correct
16 Correct 634 ms 44568 KB Output is correct
17 Correct 647 ms 44052 KB Output is correct
18 Correct 624 ms 41068 KB Output is correct
19 Correct 607 ms 44816 KB Output is correct
20 Correct 610 ms 44648 KB Output is correct
21 Correct 684 ms 44664 KB Output is correct
22 Correct 681 ms 44536 KB Output is correct
23 Correct 684 ms 44000 KB Output is correct
24 Correct 689 ms 40816 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 2816 KB Output is correct
11 Correct 3 ms 2688 KB Output is correct
12 Correct 3 ms 2688 KB Output is correct
13 Correct 2 ms 2688 KB Output is correct
14 Correct 3 ms 2688 KB Output is correct
15 Correct 3 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 120 ms 2936 KB Output is correct
20 Correct 124 ms 2936 KB Output is correct
21 Correct 138 ms 2816 KB Output is correct
22 Correct 178 ms 2936 KB Output is correct
23 Correct 868 ms 3448 KB Output is correct
24 Correct 1020 ms 3320 KB Output is correct
25 Correct 1118 ms 3632 KB Output is correct
26 Correct 1353 ms 3584 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 2944 KB Output is correct
31 Correct 79 ms 3832 KB Output is correct
32 Correct 2 ms 2688 KB Output is correct
33 Correct 2 ms 2688 KB Output is correct
34 Correct 4 ms 2688 KB Output is correct
35 Correct 14 ms 2816 KB Output is correct
36 Correct 25 ms 3200 KB Output is correct
37 Correct 122 ms 4252 KB Output is correct
38 Correct 7 ms 3072 KB Output is correct
39 Correct 14 ms 3072 KB Output is correct
40 Correct 111 ms 3072 KB Output is correct
41 Correct 44 ms 4864 KB Output is correct
42 Correct 180 ms 6008 KB Output is correct
43 Correct 219 ms 36196 KB Output is correct
44 Correct 223 ms 36196 KB Output is correct
45 Correct 243 ms 36196 KB Output is correct
46 Correct 311 ms 36452 KB Output is correct
47 Correct 729 ms 37996 KB Output is correct
48 Correct 16 ms 2816 KB Output is correct
49 Correct 10 ms 2944 KB Output is correct
50 Correct 24 ms 3456 KB Output is correct
51 Correct 46 ms 4216 KB Output is correct
52 Correct 7 ms 3712 KB Output is correct
53 Correct 12 ms 3840 KB Output is correct
54 Correct 35 ms 4504 KB Output is correct
55 Correct 56 ms 5112 KB Output is correct
56 Correct 28 ms 7928 KB Output is correct
57 Correct 33 ms 8056 KB Output is correct
58 Correct 57 ms 8312 KB Output is correct
59 Correct 92 ms 8568 KB Output is correct
60 Correct 54 ms 12536 KB Output is correct
61 Correct 62 ms 12536 KB Output is correct
62 Correct 88 ms 12792 KB Output is correct
63 Correct 114 ms 13048 KB Output is correct
64 Correct 173 ms 13176 KB Output is correct
65 Correct 570 ms 32248 KB Output is correct
66 Correct 635 ms 32380 KB Output is correct
67 Correct 578 ms 32376 KB Output is correct
68 Correct 576 ms 32376 KB Output is correct
69 Correct 610 ms 32756 KB Output is correct
70 Correct 596 ms 34716 KB Output is correct
71 Correct 586 ms 37112 KB Output is correct
72 Correct 643 ms 37172 KB Output is correct
73 Correct 639 ms 37112 KB Output is correct
74 Correct 624 ms 37112 KB Output is correct
75 Correct 644 ms 37364 KB Output is correct
76 Correct 688 ms 38252 KB Output is correct
77 Correct 620 ms 44768 KB Output is correct
78 Correct 667 ms 44792 KB Output is correct
79 Correct 637 ms 44668 KB Output is correct
80 Correct 634 ms 44568 KB Output is correct
81 Correct 647 ms 44052 KB Output is correct
82 Correct 624 ms 41068 KB Output is correct
83 Correct 607 ms 44816 KB Output is correct
84 Correct 610 ms 44648 KB Output is correct
85 Correct 684 ms 44664 KB Output is correct
86 Correct 681 ms 44536 KB Output is correct
87 Correct 684 ms 44000 KB Output is correct
88 Correct 689 ms 40816 KB Output is correct
89 Incorrect 581 ms 34808 KB Output isn't correct
90 Halted 0 ms 0 KB -