oj.uz

Submission #950769

# Submission time Handle Problem Language Result Execution time Memory
950769 2024-03-20T16:26:27 Z Vladth11 ICC (CEOI16_icc) C++14
100 / 100
 83 ms 632 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

#include "icc.h"

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const ll NMAX = 101;
const ll INF = (1LL << 58);
const ll nrbits = 20;
const ll MOD = 998244353;
const int VMAX = 10;

int a[NMAX];
int b[NMAX];

set <int> st[NMAX];

int pa[NMAX];
int n;
int dsu(int x){
    if(pa[x] == x)
        return x;
    return pa[x] = dsu(pa[x]);
}

void merge(int a, int b){
    a = dsu(a);
    b = dsu(b);
    pa[b] = a;
    for(auto x : st[b])
        st[a].insert(x);
    st[b].clear();
}

int sol1, sol2;
int auxiliar[NMAX];
int nrAux, nrA, nrB;

int divideA(int st, int dr){
    if(st == dr)
        return a[st];
    int mid = (st + dr) / 2;
    nrAux = 0;
    for(int i = st; i <= mid; i++){
        auxiliar[nrAux++] = a[i];
    }
    int rez = query(nrAux, nrB, auxiliar, b);
    if(rez)
        return divideA(st, mid);
    return divideA(mid + 1, dr);
}

int divideB(int st, int dr){
    if(st == dr)
        return b[st];
    int mid = (st + dr) / 2;
    nrAux = 0;
    for(int i = st; i <= mid; i++){
        auxiliar[nrAux++] = b[i];
    }
    int rez = query(nrA, nrAux, a, auxiliar);
    if(rez)
        return divideB(st, mid);
    return divideB(mid + 1, dr);
}


int comp[NMAX];

void newEdge(){
    vector <int> cn;
    for(int i = 1; i <= n; i++){
        int rt = dsu(i);
        if(rt != i) continue;
        cn.push_back(i);
    }
    int acum = 0;
    for(int j = 0; j < 7; j++){
        nrA = 0;
        nrB = 0;
        for(int i = 0; i < cn.size(); i++){
            int x = cn[i];
            if(i & (1 << j)){
                for(auto y : st[x]){
                    a[nrA++] = y;
                    comp[y] = i;
                }
            }else{
                for(auto y : st[x]){
                    b[nrB++] = y;
                    comp[y] = i;
                }
            }
        }
        int rez = query(nrA, nrB, a, b);
        if(rez){
            acum = j;
            break;
        }
    }
    int primul = divideA(0, nrA - 1);
    vector <int> ramas;
    for(int i = 0; i < nrB; i++)
        ramas.push_back(b[i]);
    nrB = 0;
    for(auto x : ramas){
        int ok = 1;
        for(int j = 0; j < acum; j++){
            if((comp[x] & (1 << j)) != (comp[primul] & (1 << j))){
                ok = 0;
            }
        }
        if(ok){
            b[nrB++] = x;
        }
    }
    int doilea = divideB(0, nrB - 1);
    setRoad(primul, doilea);
    merge(primul, doilea);
}

void run(int N){
    n = N;
    int i;
    for(i = 1; i <= n; i++){
        pa[i] = i;
        st[i].insert(i);
    }
    for(i = 1; i < n; i++){
        newEdge();
    }
}

Compilation message

icc.cpp: In function 'void newEdge()':
icc.cpp:87:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int i = 0; i < cn.size(); i++){
      |                        ~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Ok! 97 queries used.
2 Correct 4 ms 604 KB Ok! 93 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 604 KB Ok! 498 queries used.
2 Correct 28 ms 616 KB Ok! 464 queries used.
3 Correct 22 ms 604 KB Ok! 466 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 632 KB Ok! 1273 queries used.
2 Correct 67 ms 600 KB Ok! 1138 queries used.
3 Correct 71 ms 604 KB Ok! 1168 queries used.
4 Correct 75 ms 600 KB Ok! 1222 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 604 KB Ok! 1173 queries used.
2 Correct 79 ms 604 KB Ok! 1213 queries used.
3 Correct 68 ms 600 KB Ok! 1162 queries used.
4 Correct 73 ms 624 KB Ok! 1207 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 604 KB Ok! 1145 queries used.
2 Correct 83 ms 624 KB Ok! 1115 queries used.
3 Correct 79 ms 620 KB Ok! 1131 queries used.
4 Correct 73 ms 624 KB Ok! 1238 queries used.
5 Correct 78 ms 600 KB Ok! 1278 queries used.
6 Correct 79 ms 604 KB Ok! 1292 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 600 KB Ok! 1138 queries used.
2 Correct 70 ms 620 KB Ok! 1138 queries used.