oj.uz

Submission #362431

# Submission time Handle Problem Language Result Execution time Memory
362431 2021-02-03T07:47:51 Z alextodoran ICC (CEOI16_icc) C++17
61 / 100
 164 ms 640 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

typedef long long ll;

const int N_MAX = 102;

const int BITS = 7;

int query (int sa, int sb, int a[], int b[]);

void setRoad (int a, int b);

vector <int> edges[N_MAX];

vector <int> component[N_MAX];
int cntComponents;

bool visited[N_MAX];

void dfs (int u)
{
    visited[u] = true;
    component[cntComponents].push_back(u);
    for(int v : edges[u])
        if(visited[v] == false)
            dfs(v);
}

int a[N_MAX], b[N_MAX];

int ca[N_MAX], cb[N_MAX];

void run (int n)
{
    for(int t = 1; t < n; t++)
    {
        int U, V;
        for(int i = 1; i <= n; i++)
            visited[i] = false;
        for(int i = 1; i <= n; i++)
            if(visited[i] == false)
            {
                cntComponents++;
                dfs(i);
            }
        int cntca, cntcb;
        for(int bit = 0; bit < BITS; bit++)
        {
            int cnta = 0, cntb = 0;
            for(int i = 1; i <= cntComponents; i++)
                if((i >> bit) & 1)
                {
                    for(int u : component[i])
                        a[cnta++] = u;
                }
                else
                {
                    for(int u : component[i])
                        b[cntb++] = u;
                }
            if(query(cnta, cntb, a, b) == true)
            {
                cntca = 0;
                cntcb = 0;
                for(int i = 1; i <= cntComponents; i++)
                    if((i >> bit) & 1)
                        ca[++cntca] = i;
                    else
                        cb[++cntcb] = i;
                break;
            }
        }
        int c1, c2;
        int l, r;
        l = 1;
        r = cntca;
        while(l < r)
        {
            int mid = ((l + r) >> 1);
            int cnta = 0, cntb = 0;
            for(int i = l; i <= mid; i++)
                for(int u : component[ca[i]])
                    a[cnta++] = u;
            for(int i = 1; i <= cntcb; i++)
                for(int u : component[cb[i]])
                    b[cntb++] = u;
            if(query(cnta, cntb, a, b) == true)
                r = mid;
            else
                l = mid + 1;
        }
        c1 = ca[l];
        l = 1;
        r = cntcb;
        while(l < r)
        {
            int mid = ((l + r) >> 1);
            int cnta = 0, cntb = 0;
            for(int i = 1; i <= cntca; i++)
                for(int u : component[ca[i]])
                    a[cnta++] = u;
            for(int i = l; i <= mid; i++)
                for(int u : component[cb[i]])
                    b[cntb++] = u;
            if(query(cnta, cntb, a, b) == true)
                r = mid;
            else
                l = mid + 1;
        }
        c2 = cb[l];
        l = 0;
        r = (int)component[c1].size() - 1;
        while(l < r)
        {
            int mid = ((l + r) >> 1);
            int cnta = 0, cntb = 0;
            for(int i = l; i <= mid; i++)
                a[cnta++] = component[c1][i];
            for(int u : component[c2])
                b[cntb++] = u;
            if(query(cnta, cntb, a, b) == true)
                r = mid;
            else
                l = mid + 1;
        }
        U = component[c1][l];
        l = 0;
        r = (int)component[c2].size() - 1;
        while(l < r)
        {
            int mid = ((l + r) >> 1);
            int cnta = 0, cntb = 0;
            for(int u : component[c1])
                a[cnta++] = u;
            for(int i = l; i <= mid; i++)
                b[cntb++] = component[c2][i];
            if(query(cnta, cntb, a, b) == true)
                r = mid;
            else
                l = mid + 1;
        }
        V = component[c2][r];
        setRoad(U, V);
        edges[U].push_back(V);
        edges[V].push_back(U);
        for(int i = 1; i <= cntComponents; i++)
            component[i].clear();
        cntComponents = 0;
    }
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:57:20: warning: 'cntcb' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |         int cntca, cntcb;
      |                    ^~~~~
icc.cpp:57:13: warning: 'cntca' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |         int cntca, cntcb;
      |             ^~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 492 KB Ok! 114 queries used.
2 Correct 7 ms 492 KB Ok! 111 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 492 KB Ok! 672 queries used.
2 Correct 44 ms 492 KB Ok! 644 queries used.
3 Correct 46 ms 492 KB Ok! 673 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 492 KB Ok! 1789 queries used.
2 Correct 142 ms 620 KB Ok! 1568 queries used.
3 Correct 162 ms 492 KB Ok! 1912 queries used.
4 Correct 153 ms 584 KB Ok! 1772 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 620 KB Ok! 1845 queries used.
2 Correct 158 ms 492 KB Ok! 1832 queries used.
3 Correct 160 ms 492 KB Ok! 1817 queries used.
4 Correct 154 ms 492 KB Ok! 1810 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 492 KB Too many queries! 1846 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 155 ms 640 KB Too many queries! 1795 out of 1625
2 Halted 0 ms 0 KB -