oj.uz

Submission #545190

# Submission time Handle Problem Language Result Execution time Memory
545190 2022-04-03T23:02:24 Z chonka Reconstruction Project (JOI22_reconstruction) C++
100 / 100
 2312 ms 228076 KB 
#include<bits/stdc++.h>
using namespace std ;

#define MAXN 501
#define MAXK 100007
#define inf 1000000007



int n , k ;
struct edge {
    int x , y , w ;
};
edge a[ MAXK ] ;

class uf {
public :
    short prv[ MAXN ] , rnk[ MAXN ] ;
    int edge_cnt ;
    void init ( ) {
        for ( int i = 1 ; i <= n ; ++ i ) {
            prv[ i ] = -1 , rnk[ i ] = 0 ;
        }
        edge_cnt = 0 ;
    }
    int get ( int x ) {
        if ( prv[ x ] == -1 ) { return x ; }
        int y = get ( prv[ x ] ) ;
        prv[ x ] = y ;
        return y ;
    }
    void unite ( int x , int y ) {
        int h1 = get ( x ) , h2 = get ( y ) ;
        if ( h1 != h2 ) {
            ++ edge_cnt ;
            if ( rnk[ h1 ] >= rnk[ h2 ] ) {
                rnk[ h1 ] += ( rnk[ h1 ] == rnk[ h2 ] ) ;
                prv[ h2 ] = h1 ;
            }
            else {
                prv[ h1 ] = h2 ;
            }
        }
    }
};

uf hh[ MAXK ] ;
int act[ MAXN ] ;



int range_st[ MAXK ] , range_en[ MAXK ] ;

struct event {
    int pos ;
    int chsum , chcoef ;
    event ( ) { pos = chsum = chcoef = 0 ; }
    event ( int _pos , int _chsum , int _chcoef ) {
        pos = _pos , chsum = _chsum , chcoef = _chcoef ;
    }
};
vector < event > srt ;

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    cin >> n >> k ;
    for ( int i = 1 ; i <= k ; ++ i ) {
        cin >> a[ i ].x >> a[ i ].y >> a[ i ].w ;
    }
    auto cmp = [ & ] ( edge p1 , edge p2 ) {
        return ( p1.w < p2.w ) ;
    };
    sort ( a + 1 , a + k + 1 , cmp ) ;
    for ( int i = 0 ; i <= k ; ++ i ) {
        hh[ i ].init ( ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        act[ i ] = 0 ;
    }
    for ( int i = 1 ; i <= k ; ++ i ) {
        range_st[ i ] = 0 ;
        for ( int j = 1 ; j < n ; ++ j ) {
            int id = act[ j ] ;
            if ( id == 0 ) { break ; }
            if ( hh[ id ].get ( a[ i ].x ) == hh[ id ].get ( a[ i ].y ) ) {
                range_st[ i ] = a[ id ].w ;
                break ;
            }
        }
        for ( int j = n - 2 ; j >= 1 ; -- j ) {
            int id = act[ j ] ;
            if ( id != 0 ) {
                hh[ id ].unite ( a[ i ].x , a[ i ].y ) ;
                if ( hh[ id ].edge_cnt > j ) {
                    act[ j + 1 ] = id ;
                }
            }
        }
        hh[ i ].unite ( a[ i ].x , a[ i ].y ) ;
        act[ 1 ] = i ;
    }
    for ( int i = 0 ; i <= k ; ++ i ) {
        hh[ i ].init ( ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        act[ i ] = 0 ;
    }

    for ( int i = k ; i >= 1 ; -- i ) {
        range_en[ i ] = inf ;
        for ( int j = 1 ; j < n ; ++ j ) {
            int id = act[ j ] ;
            if ( id == 0 ) { break ; }
            if ( hh[ id ].get ( a[ i ].x ) == hh[ id ].get ( a[ i ].y ) ) {
                range_en[ i ] = a[ id ].w ;
                break ;
            }
        }
        for ( int j = n - 2 ; j >= 1 ; -- j ) {
            int id = act[ j ] ;
            if ( id != 0 ) {
                hh[ id ].unite ( a[ i ].x , a[ i ].y ) ;
                if ( hh[ id ].edge_cnt > j ) {
                    act[ j + 1 ] = id ;
                }
            }
        }
        for ( int j = 1 ; j < n ; ++ j ) {
            int id = act[ j ] ;
            if ( id != 0 ) {
                hh[ id ].unite ( a[ i ].x , a[ i ].y ) ;
                if ( hh[ id ].edge_cnt > j ) {
                    act[ j + 1 ] = id ;
                }
            }
        }
        hh[ i ].unite ( a[ i ].x , a[ i ].y ) ;
        act[ 1 ] = i ;
    }


    for ( int i = 1 ; i <= k ; ++ i ) {
        // printf ( "%d %d %d --> %d %d\n" , a[ i ].x , a[ i ].y , a[ i ].w , range_st[ i ] , range_en[ i ] ) ;
        int st = range_st[ i ] ;
        if ( st != 0 ) {
            if ( ( ( a[ i ].w - st ) % 2 ) == 1 ) {
                ++ st ;
            }
            st = ( a[ i ].w + st ) / 2 ;
        }
        int en = range_en[ i ] ;
        if ( en != inf ) {
            if ( ( ( en - a[ i ].w ) % 2 ) == 0 ) {
                -- en ;
            }
            en = ( a[ i ].w + en ) / 2 ;
        }
        srt.push_back ( event ( st , a[ i ].w , -1 ) ) ;
        srt.push_back ( event ( a[ i ].w , -a[ i ].w , 1 ) ) ;

        srt.push_back ( event ( a[ i ].w , -a[ i ].w , 1 ) ) ;
        srt.push_back ( event ( en + 1 , a[ i ].w , -1 ) ) ;
    }
    auto ev_cmp = [ & ] ( event p1 , event p2 ) {
        return ( p1.pos < p2.pos ) ;
    };
    sort ( srt.begin ( ) , srt.end ( ) , ev_cmp ) ;
    int q ;
    cin >> q ;
    int lst = -1 ;
    int sz = srt.size ( ) ;
    long long totsm = 0 ;
    long long totcoef = 0 ;
    while ( q -- ) {
        int wh ; cin >> wh ;
        while ( lst + 1 < sz && srt[ lst + 1 ].pos <= wh ) {
            ++ lst ;
            totsm += srt[ lst ].chsum ;
            totcoef += srt[ lst ].chcoef ;
        }
        cout << totsm + totcoef * wh << "\n" ;
    }
    return 0 ;
}

Subtask #1
3.0 / 3.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2312 ms 206688 KB Output is correct
21 Correct 1746 ms 204984 KB Output is correct
22 Correct 1760 ms 205012 KB Output is correct
23 Correct 1899 ms 205044 KB Output is correct
24 Correct 2055 ms 205044 KB Output is correct
25 Correct 2118 ms 205140 KB Output is correct
26 Correct 2119 ms 206744 KB Output is correct
27 Correct 2154 ms 206616 KB Output is correct
28 Correct 2092 ms 206800 KB Output is correct
29 Correct 2139 ms 206660 KB Output is correct
30 Correct 2065 ms 206860 KB Output is correct
31 Correct 2031 ms 206776 KB Output is correct
32 Correct 2096 ms 206844 KB Output is correct
33 Correct 2063 ms 205176 KB Output is correct
34 Correct 2037 ms 206864 KB Output is correct
35 Correct 2063 ms 206728 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1964 ms 225952 KB Output is correct
5 Correct 1925 ms 225952 KB Output is correct
6 Correct 1921 ms 226068 KB Output is correct
7 Correct 1254 ms 227960 KB Output is correct
8 Correct 1002 ms 227912 KB Output is correct
9 Correct 893 ms 228076 KB Output is correct
10 Correct 1907 ms 226120 KB Output is correct
11 Correct 989 ms 227852 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 193 ms 23692 KB Output is correct
21 Correct 192 ms 18560 KB Output is correct
22 Correct 195 ms 21096 KB Output is correct
23 Correct 198 ms 20956 KB Output is correct
24 Correct 196 ms 20968 KB Output is correct
25 Correct 192 ms 20968 KB Output is correct
26 Correct 193 ms 20944 KB Output is correct
27 Correct 192 ms 21152 KB Output is correct
28 Correct 198 ms 20996 KB Output is correct
29 Correct 199 ms 20952 KB Output is correct
30 Correct 200 ms 18432 KB Output is correct
31 Correct 195 ms 20940 KB Output is correct
32 Correct 199 ms 21640 KB Output is correct
33 Correct 195 ms 20828 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2312 ms 206688 KB Output is correct
21 Correct 1746 ms 204984 KB Output is correct
22 Correct 1760 ms 205012 KB Output is correct
23 Correct 1899 ms 205044 KB Output is correct
24 Correct 2055 ms 205044 KB Output is correct
25 Correct 2118 ms 205140 KB Output is correct
26 Correct 2119 ms 206744 KB Output is correct
27 Correct 2154 ms 206616 KB Output is correct
28 Correct 2092 ms 206800 KB Output is correct
29 Correct 2139 ms 206660 KB Output is correct
30 Correct 2065 ms 206860 KB Output is correct
31 Correct 2031 ms 206776 KB Output is correct
32 Correct 2096 ms 206844 KB Output is correct
33 Correct 2063 ms 205176 KB Output is correct
34 Correct 2037 ms 206864 KB Output is correct
35 Correct 2063 ms 206728 KB Output is correct
36 Correct 2049 ms 205212 KB Output is correct
37 Correct 1586 ms 205152 KB Output is correct
38 Correct 1640 ms 205060 KB Output is correct
39 Correct 1759 ms 205236 KB Output is correct
40 Correct 1962 ms 205132 KB Output is correct
41 Correct 2005 ms 205324 KB Output is correct
42 Correct 2116 ms 205192 KB Output is correct
43 Correct 2105 ms 205300 KB Output is correct
44 Correct 2003 ms 205092 KB Output is correct
45 Correct 2021 ms 204988 KB Output is correct
46 Correct 2055 ms 205144 KB Output is correct
47 Correct 2045 ms 205040 KB Output is correct
48 Correct 2068 ms 205072 KB Output is correct
49 Correct 2023 ms 205216 KB Output is correct
50 Correct 2020 ms 205272 KB Output is correct
51 Correct 2024 ms 205268 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2312 ms 206688 KB Output is correct
21 Correct 1746 ms 204984 KB Output is correct
22 Correct 1760 ms 205012 KB Output is correct
23 Correct 1899 ms 205044 KB Output is correct
24 Correct 2055 ms 205044 KB Output is correct
25 Correct 2118 ms 205140 KB Output is correct
26 Correct 2119 ms 206744 KB Output is correct
27 Correct 2154 ms 206616 KB Output is correct
28 Correct 2092 ms 206800 KB Output is correct
29 Correct 2139 ms 206660 KB Output is correct
30 Correct 2065 ms 206860 KB Output is correct
31 Correct 2031 ms 206776 KB Output is correct
32 Correct 2096 ms 206844 KB Output is correct
33 Correct 2063 ms 205176 KB Output is correct
34 Correct 2037 ms 206864 KB Output is correct
35 Correct 2063 ms 206728 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 0 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1964 ms 225952 KB Output is correct
40 Correct 1925 ms 225952 KB Output is correct
41 Correct 1921 ms 226068 KB Output is correct
42 Correct 1254 ms 227960 KB Output is correct
43 Correct 1002 ms 227912 KB Output is correct
44 Correct 893 ms 228076 KB Output is correct
45 Correct 1907 ms 226120 KB Output is correct
46 Correct 989 ms 227852 KB Output is correct
47 Correct 0 ms 340 KB Output is correct
48 Correct 193 ms 23692 KB Output is correct
49 Correct 192 ms 18560 KB Output is correct
50 Correct 195 ms 21096 KB Output is correct
51 Correct 198 ms 20956 KB Output is correct
52 Correct 196 ms 20968 KB Output is correct
53 Correct 192 ms 20968 KB Output is correct
54 Correct 193 ms 20944 KB Output is correct
55 Correct 192 ms 21152 KB Output is correct
56 Correct 198 ms 20996 KB Output is correct
57 Correct 199 ms 20952 KB Output is correct
58 Correct 200 ms 18432 KB Output is correct
59 Correct 195 ms 20940 KB Output is correct
60 Correct 199 ms 21640 KB Output is correct
61 Correct 195 ms 20828 KB Output is correct
62 Correct 2049 ms 205212 KB Output is correct
63 Correct 1586 ms 205152 KB Output is correct
64 Correct 1640 ms 205060 KB Output is correct
65 Correct 1759 ms 205236 KB Output is correct
66 Correct 1962 ms 205132 KB Output is correct
67 Correct 2005 ms 205324 KB Output is correct
68 Correct 2116 ms 205192 KB Output is correct
69 Correct 2105 ms 205300 KB Output is correct
70 Correct 2003 ms 205092 KB Output is correct
71 Correct 2021 ms 204988 KB Output is correct
72 Correct 2055 ms 205144 KB Output is correct
73 Correct 2045 ms 205040 KB Output is correct
74 Correct 2068 ms 205072 KB Output is correct
75 Correct 2023 ms 205216 KB Output is correct
76 Correct 2020 ms 205272 KB Output is correct
77 Correct 2024 ms 205268 KB Output is correct
78 Correct 2251 ms 213628 KB Output is correct
79 Correct 1742 ms 215728 KB Output is correct
80 Correct 1808 ms 214752 KB Output is correct
81 Correct 1966 ms 214664 KB Output is correct
82 Correct 2109 ms 213784 KB Output is correct
83 Correct 2149 ms 213916 KB Output is correct
84 Correct 2240 ms 213924 KB Output is correct
85 Correct 2171 ms 213868 KB Output is correct
86 Correct 2203 ms 213808 KB Output is correct
87 Correct 2191 ms 215600 KB Output is correct
88 Correct 2188 ms 213664 KB Output is correct
89 Correct 2186 ms 213896 KB Output is correct
90 Correct 2186 ms 213756 KB Output is correct
91 Correct 2217 ms 213644 KB Output is correct
92 Correct 2219 ms 216568 KB Output is correct
93 Correct 2168 ms 214836 KB Output is correct