oj.uz

Submission #950757

# Submission time Handle Problem Language Result Execution time Memory
950757 2024-03-20T16:11:45 Z Vladth11 ICC (CEOI16_icc) C++14
7 / 100
 72 ms 604 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 5 ms 604 KB Ok! 98 queries used.
2 Correct 5 ms 604 KB Ok! 100 queries used.

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 600 KB Ok! 523 queries used.
2 Incorrect 1 ms 600 KB Wrong road!
3 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 604 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 604 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 604 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 600 KB Wrong road!
2 Halted 0 ms 0 KB -