oj.uz

Submission #950758

# Submission time Handle Problem Language Result Execution time Memory
950758 2024-03-20T16:12:11 Z Vladth11 ICC (CEOI16_icc) C++14
90 / 100
 109 ms 848 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);
}
 
void newEdge(){
    vector <int> cn;
    sol1 = sol2 = -1;
    for(int i = 1; i <= n; i++){
        int rt = dsu(i);
        if(rt != i) continue;
        cn.push_back(i);
    }
    for(int j = 0; j <= (int)log2(cn.size()); 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;
                }
            }else{
                for(auto y : st[x]){
                    b[nrB++] = y;
                }
            }
        }
        int rez = query(nrA, nrB, a, b);
        if(rez){
            break;
        }
    }
    int primul = divideA(0, nrA - 1);
    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:85:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int i = 0; i < cn.size(); i++){
      |                        ~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Ok! 98 queries used.
2 Correct 4 ms 604 KB Ok! 100 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 640 KB Ok! 523 queries used.
2 Correct 32 ms 604 KB Ok! 659 queries used.
3 Correct 30 ms 604 KB Ok! 658 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 604 KB Ok! 1406 queries used.
2 Correct 91 ms 616 KB Ok! 1612 queries used.
3 Correct 105 ms 604 KB Ok! 1577 queries used.
4 Correct 88 ms 628 KB Ok! 1484 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 616 KB Ok! 1500 queries used.
2 Correct 87 ms 604 KB Ok! 1485 queries used.
3 Correct 92 ms 604 KB Ok! 1636 queries used.
4 Correct 109 ms 600 KB Ok! 1456 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 620 KB Ok! 1623 queries used.
2 Correct 101 ms 848 KB Ok! 1608 queries used.
3 Correct 94 ms 600 KB Ok! 1668 queries used.
4 Correct 93 ms 620 KB Ok! 1636 queries used.
5 Correct 83 ms 604 KB Ok! 1423 queries used.
6 Correct 90 ms 628 KB Ok! 1530 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 604 KB Too many queries! 1644 out of 1625
2 Halted 0 ms 0 KB -