oj.uz

Submission #1027934

# Submission time Handle Problem Language Result Execution time Memory
1027934 2024-07-19T11:46:30 Z serifefedartar ICC (CEOI16_icc) C++17
18 / 100
 215 ms 684 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 20
const ll MOD = 1e9 + 7;
const ll MAXN = 105;

int par[MAXN], sz[MAXN], temp1[MAXN], temp2[MAXN];
int find(int node) {
    if (node == par[node])
        return node;
    return par[node] = find(par[node]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return ;
    if (sz[b] > sz[a])
        swap(a, b);
    sz[a] += sz[b];
    par[b] = a;
}

int qry(int sz1, int sz2, vector<int> A, vector<int> B) {
    for (int i = 0; i < sz1; i++)
        temp1[i] = A[i];
    for (int i = 0; i < sz2; i++)
        temp2[i] = B[i];
    return query(sz1, sz2, temp1, temp2);
}

bool control = true;
void dac(vector<vector<int>> A, vector<vector<int>> B) {
    if (!control || A.size() == 0 || B.size() == 0)
        return ; 

    vector<int> AA, BB;
    for (auto u : A)
        for (auto v : u)
            AA.push_back(v);
    for (auto u : B)
        for (auto v : u)
            BB.push_back(v);

    if (qry(AA.size(), BB.size(), AA, BB)) {

        while (AA.size() > 1 || BB.size() > 1) {
            vector<int> A1, A2;
            vector<int> B1, B2;
            for (int i = 0; i < AA.size()/2; i++)
                A1.push_back(AA[i]);
            for (int i = AA.size()/2; i < AA.size(); i++)
                A2.push_back(AA[i]);
            for (int i = 0; i < BB.size()/2; i++)
                B1.push_back(BB[i]);
            for (int i = BB.size()/2; i < BB.size(); i++)
                B2.push_back(BB[i]);

            if (qry(A1.size(), B1.size(), A1, B1))
                AA = A1, BB = B1;
            else if (qry(A1.size(), B2.size(), A1, B2))
                AA = A1, BB = B2;
            else if (qry(A2.size(), B1.size(), A2, B1))
                AA = A2, BB = B1;
            else
                AA = A2, BB = B2;
        }

        setRoad(AA[0], BB[0]);
        unite(AA[0], BB[0]);
        control = false;
    } else {
        vector<vector<int>> A1, A2;
        vector<vector<int>> B1, B2;
        for (int i = 0; i < (int)A.size() / 2; i++)
            A1.push_back(A[i]);
        for (int i = (int)A.size() / 2; i < (int)A.size(); i++)
            A2.push_back(A[i]);
        for (int i = 0; i < (int)B.size() / 2; i++)
            B1.push_back(B[i]);
        for (int i = (int)B.size() / 2; i < (int)B.size(); i++)
            B2.push_back(B[i]);
        dac(A1, A2);
        dac(B1, B2);
    }
}

int n;
void solve() {
    map<int, vector<int>> mp;
    for (int i = 1; i <= n; i++)
        mp[find(i)].push_back(i);

    vector<vector<int>> temp;
    for (auto u : mp)
        temp.push_back(u.s);

    vector<vector<int>> A, B;
    for (int i = 0; i < (int)temp.size() / 2; i++)
        A.push_back(temp[i]);
    for (int i = temp.size() / 2; i < (int)temp.size(); i++)
        B.push_back(temp[i]);
    control = true;
    dac(A, B);
}

void run(int N) {
    n = N;
    for (int i = 1; i <= N; i++)
        sz[i] = 1, par[i] = i;
    for (int i = 1; i < N; i++)
        solve();
}

Compilation message

icc.cpp: In function 'void dac(std::vector<std::vector<int> >, std::vector<std::vector<int> >)':
icc.cpp:57:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for (int i = 0; i < AA.size()/2; i++)
      |                             ~~^~~~~~~~~~~~~
icc.cpp:59:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             for (int i = AA.size()/2; i < AA.size(); i++)
      |                                       ~~^~~~~~~~~~~
icc.cpp:61:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             for (int i = 0; i < BB.size()/2; i++)
      |                             ~~^~~~~~~~~~~~~
icc.cpp:63:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             for (int i = BB.size()/2; i < BB.size(); i++)
      |                                       ~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 600 KB Ok! 179 queries used.
2 Correct 6 ms 600 KB Ok! 195 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 604 KB Ok! 1145 queries used.
2 Correct 64 ms 648 KB Ok! 1872 queries used.
3 Correct 63 ms 652 KB Ok! 1918 queries used.

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 215 ms 676 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 178 ms 664 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 149 ms 684 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 137 ms 604 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -