oj.uz

Submission #44723

# Submission time Handle Problem Language Result Execution time Memory
44723 2018-04-05T13:47:56 Z bogdan10bos ICC (CEOI16_icc) C++14
61 / 100
 238 ms 1188 KB 
#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

int f[105];
vector<int> comp, nodes[105];
int F(int x)
{
    if(f[x] == x)   return x;
    return f[x] = F(f[x]);
}

void init(int N)
{
    comp.clear();
    for(int i = 1; i <= N; i++)
    {
        nodes[i].clear();
        nodes[i].push_back(i);
        f[i] = i;
        comp.push_back(i);
    }
}

void newRoad(int x, int y)
{
    setRoad(x, y);
    int fx = F(x), fy = F(y);
    f[fy] = fx;
    for(auto x: nodes[fy])  nodes[fx].push_back(x);
    for(int i = 0; i < comp.size(); i++)
        if(comp[i] == fy)
        {
            comp.erase(comp.begin() + i);
            return;
        }
}

void solve(vector<int> A, vector<int> B)
{
    if(A.size() == 1 && B.size() == 1)
    {
        newRoad(A[0], B[0]);
        return;
    }
    if(A.size() == 1)
    {
        solve(B, A);
        return;
    }

    int mij = A.size() / 2;
    vector<int> X, Y;
    for(int i = 0; i < mij; i++)    X.push_back(A[i]);
    for(int i = mij; i < A.size(); i++) Y.push_back(A[i]);

    int q = query(X.size(), B.size(), X.data(), B.data());
    if(q)   solve(X, B);
    else    solve(Y, B);
}

int queryComp(vector<int> A, vector<int> B)
{
    if(A.size() == 0 || B.size() == 0)  return 0;
    vector<int> a, b;
    for(auto x: A)
        for(auto y: nodes[x])
            a.push_back(y);
    for(auto x: B)
        for(auto y: nodes[x])
            b.push_back(y);
    return query(a.size(), b.size(), a.data(), b.data());
}

void solveComp(vector<int> A, vector<int> B)
{
    if(A.size() == 1 && B.size() == 1)
    {
        solve(nodes[ A[0] ], nodes[ B[0] ]);
        return;
    }
    if(A.size() == 1)
    {
        solveComp(B, A);
        return;
    }

    int mij = A.size() / 2;
    vector<int> X, Y;
    for(int i = 0; i < mij; i++)    X.push_back(A[i]);
    for(int i = mij; i < A.size(); i++) Y.push_back(A[i]);

    int q = queryComp(X, B);
    if(q)   solveComp(X, B);
    else    solveComp(Y, B);
}

void findRoad()
{
    for(int b = 0; (1 << b) < comp.size(); b++)
    {
        vector<int> B[2];
        for(int i = 0; i < comp.size(); i++)
            B[ (i >> b) & 1 ].push_back( comp[i] );
        int q = queryComp(B[0], B[1]);
        if(q)
        {
            solveComp(B[0], B[1]);
            return;
        }
    }
}

void run(int N)
{
    init(N);
    while( comp.size() > 1 )
        findRoad();
}

Compilation message

icc.cpp: In function 'void newRoad(int, int)':
icc.cpp:32:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < comp.size(); i++)
                    ~~^~~~~~~~~~~~~
icc.cpp: In function 'void solve(std::vector<int>, std::vector<int>)':
icc.cpp:56:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = mij; i < A.size(); i++) Y.push_back(A[i]);
                      ~~^~~~~~~~~~
icc.cpp: In function 'void solveComp(std::vector<int>, std::vector<int>)':
icc.cpp:92:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = mij; i < A.size(); i++) Y.push_back(A[i]);
                      ~~^~~~~~~~~~
icc.cpp: In function 'void findRoad()':
icc.cpp:101:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int b = 0; (1 << b) < comp.size(); b++)
                    ~~~~~~~~~^~~~~~~~~~~~~
icc.cpp:104:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < comp.size(); i++)
                        ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Ok! 114 queries used.
2 Correct 10 ms 744 KB Ok! 117 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 976 KB Ok! 660 queries used.
2 Correct 74 ms 976 KB Ok! 756 queries used.
3 Correct 59 ms 1008 KB Ok! 786 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 1028 KB Ok! 1823 queries used.
2 Correct 174 ms 1028 KB Ok! 1967 queries used.
3 Correct 176 ms 1028 KB Ok! 1965 queries used.
4 Correct 238 ms 1040 KB Ok! 1868 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 1048 KB Ok! 1899 queries used.
2 Correct 209 ms 1100 KB Ok! 1894 queries used.
3 Correct 181 ms 1188 KB Ok! 1951 queries used.
4 Correct 167 ms 1188 KB Ok! 1863 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 1188 KB Too many queries! 1943 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 208 ms 1188 KB Too many queries! 1951 out of 1625
2 Halted 0 ms 0 KB -