oj.uz

Submission #166905

# Submission time Handle Problem Language Result Execution time Memory
166905 2019-12-04T14:03:03 Z Leonardo_Paes ICC (CEOI16_icc) C++11
90 / 100
 183 ms 596 KB 
#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

const int maxn = 110;

int pai[maxn], siz[maxn];

bool mark[maxn];

int find(int x){
    if(pai[x] == x){
        return x;
    }
    return pai[x] = find(pai[x]);
}

void join(int a, int b){
    a = find(a), b = find(b);

    if(a==b) return;

    if(siz[a] > siz[b]) swap(a, b);

    pai[a] = b;
    siz[b] += siz[a];
}

void run(int n){
    for(int i=0; i<n; i++){
        pai[i] = i;
        siz[i] = 1;
    }

    for(int roads = 1; roads <= (n-1); roads++){
        for(int i=0; (1 << i)<=n; i++){
            int siza = 0, sizb = 0;

            vector<int> fakea, fakeb;

            for(int j=1; j<=n; j++){
                int rep = find(j);

                if(rep & (1 << i)){
                    fakea.push_back(j);
                    siza++;
                }
                else{
                    fakeb.push_back(j);
                    sizb++;
                }
            }

            int a[siza], b[sizb];

            for(int j=0; j<fakea.size(); j++){
                a[j] = fakea[j];
            }

            for(int j=0; j<fakeb.size(); j++){
                b[j] = fakeb[j];
            }

            int ans;

            if(i==n) ans = 1;
            else ans = query(siza, sizb, a, b);

            if(ans){
                int u, v;

                int ini = 1, meio, fim = siza;

                while(ini < fim){
                    meio = (ini + fim)/2;

                    int testa[meio];

                    for(int id = 0; id<meio; id++){
                        testa[id] = a[id];
                    }

                    if(query(meio, sizb, testa, b)){
                        fim = meio;
                    }
                    else{
                        ini = meio + 1;
                    }
                }

                u = a[ini-1];

                ini = 1, fim = sizb;

                while(ini < fim){
                    meio = (ini + fim)/2;

                    int testb[meio];

                    for(int id = 0; id<meio; id++){
                        testb[id] = b[id];
                    }

                    if(query(siza, meio, a, testb)){
                        fim = meio;
                    }
                    else{
                        ini = meio + 1;
                    }
                }

                v = b[ini-1];

                join(u, v);

                setRoad(u, v);
            }
        }
    }
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:57:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0; j<fakea.size(); j++){
                          ~^~~~~~~~~~~~~
icc.cpp:61:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0; j<fakeb.size(); j++){
                          ~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Ok! 98 queries used.
2 Correct 8 ms 504 KB Ok! 96 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 504 KB Ok! 563 queries used.
2 Correct 53 ms 504 KB Ok! 706 queries used.
3 Correct 51 ms 504 KB Ok! 680 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 504 KB Ok! 1390 queries used.
2 Correct 171 ms 504 KB Ok! 1686 queries used.
3 Correct 142 ms 560 KB Ok! 1431 queries used.
4 Correct 159 ms 564 KB Ok! 1552 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 560 KB Ok! 1444 queries used.
2 Correct 148 ms 560 KB Ok! 1461 queries used.
3 Correct 172 ms 560 KB Ok! 1662 queries used.
4 Correct 143 ms 560 KB Ok! 1404 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 508 KB Ok! 1640 queries used.
2 Correct 174 ms 556 KB Ok! 1674 queries used.
3 Correct 183 ms 564 KB Ok! 1705 queries used.
4 Correct 170 ms 560 KB Ok! 1635 queries used.
5 Correct 150 ms 596 KB Ok! 1485 queries used.
6 Correct 170 ms 596 KB Ok! 1649 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 174 ms 504 KB Too many queries! 1689 out of 1625
2 Halted 0 ms 0 KB -