oj.uz

Submission #1116993

# Submission time Handle Problem Language Result Execution time Memory
1116993 2024-11-22T17:56:27 Z hyakup ICC (CEOI16_icc) C++17
100 / 100
 111 ms 848 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout << #x << " "  << x << endl;

const int maxn = 110;
const int logn = 8;

vector<int> pai( maxn ), componente[maxn];

int find( int a ){ return (( pai[a] == a ) ? a : pai[a] = find(pai[a]) ); }
void join( int a, int b ){
    a = find(a); b = find(b);
    if( a == b ) return;
    for( int x : componente[b] ) componente[a].push_back(x);
    pai[b] = a;
}

int get_node( vector<int>& va, vector<int>& vb ){
    int a[(int)va.size()], b[(int)vb.size()], pa = 0, pb = 0;
    for( int i = 0; i < va.size(); i++ ) a[pa++] = va[i];
    int l = 0, r = (int)vb.size() - 1;
    while( l < r ){
        int mid = ( l + r )/2;
        pb = 0;
        for( int i = l; i <= mid; i++ ) b[pb++] = vb[i];
        if( query( pa, pb, a, b ) ) r = mid;
        else l = mid + 1;
    }
    return vb[r];
}

int a[maxn], b[maxn];

void run( int n ){
    for( int i = 1; i <= n; i++ ){ pai[i] = i; componente[i].push_back(i); }
    for( int i = 1; i < n; i++ ){
        int pa = 0, pb = 0;
        for( int k = 0; k < logn; k++ ){
            pa = 0, pb = 0;
            for( int cur = 1; cur <= n; cur++ ) if( pai[cur] == cur ){
                for( int x : componente[cur] ){
                    if( (cur&(1<<k)) > 0 ) a[pa++] = x;
                    else b[pb++] = x;
                }
            }

            if( query( pa, pb, a, b ) ) break;
        }
        vector<int> va(pa), vb(pb);
        for( int i = 0; i < pa; i++ ) va[i] = a[i];
        for( int i = 0; i < pb; i++ ) vb[i] = b[i];

        int x = get_node( va, vb ), y = get_node( vb, va );
        setRoad( x, y );
        join( x, y ); 
    }
}

// int main(){ /////// para testar
//     int n; cin >> n;
//     run( n );
// }

Compilation message

icc.cpp: In function 'int get_node(std::vector<int>&, std::vector<int>&)':
icc.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for( int i = 0; i < va.size(); i++ ) a[pa++] = va[i];
      |                     ~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 592 KB Ok! 103 queries used.
2 Correct 4 ms 592 KB Ok! 97 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 592 KB Ok! 544 queries used.
2 Correct 24 ms 764 KB Ok! 649 queries used.
3 Correct 25 ms 640 KB Ok! 665 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 760 KB Ok! 1367 queries used.
2 Correct 74 ms 592 KB Ok! 1609 queries used.
3 Correct 68 ms 592 KB Ok! 1347 queries used.
4 Correct 75 ms 592 KB Ok! 1492 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 636 KB Ok! 1394 queries used.
2 Correct 66 ms 760 KB Ok! 1454 queries used.
3 Correct 111 ms 592 KB Ok! 1632 queries used.
4 Correct 64 ms 760 KB Ok! 1364 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 632 KB Ok! 1619 queries used.
2 Correct 80 ms 848 KB Ok! 1633 queries used.
3 Correct 75 ms 628 KB Ok! 1628 queries used.
4 Correct 75 ms 592 KB Ok! 1600 queries used.
5 Correct 67 ms 764 KB Ok! 1439 queries used.
6 Correct 74 ms 592 KB Ok! 1566 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 760 KB Ok! 1616 queries used.
2 Correct 74 ms 592 KB Ok! 1606 queries used.