oj.uz

Submission #44727

# Submission time Handle Problem Language Result Execution time Memory
44727 2018-04-05T14:09:19 Z bogdan10bos ICC (CEOI16_icc) C++14
100 / 100
 153 ms 1024 KB 
#include <bits/stdc++.h>

//#define DEBUG

#ifndef DEBUG
#include "icc.h"
#endif

using namespace std;

#ifdef DEBUG
int query(int A, int B, int *a, int *b);
void setRoad(int x, int y);
#endif

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 solveComp2(vector<int> A, vector<int> B)
{
    if(A.size() == 1)
    {
        solve(nodes[ A[0] ], nodes[ B[0] ]);
        return;
    }

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

    int q = queryComp(X[0], Y[0]);
    if(q)   solveComp2(X[0], Y[0]);
    else    solveComp2(X[1], Y[1]);
}

void findRoad()
{
    int msk = 0;
    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)   msk |= (1 << b);
    }

    vector<int> A, B;
    for(int i = 0; i < comp.size(); i++)
    {
        int j = i ^ msk;
        if(i < j && j < comp.size())
            A.push_back(comp[i]), B.push_back(comp[j]);
    }
    solveComp2(A, B);
}

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

#ifdef DEBUG

int query(int A, int B, int *a, int *b)
{
    cout << "Query:\n";
    for(int i = 0; i < A; i++)  cout << a[i] << " ";
    cout << '\n';
    for(int i = 0; i < B; i++)  cout << b[i] << " ";
    cout << '\n';

    int ans = 0;
    cin >> ans;
    return ans;
}

void setRoad(int x, int y)
{
    cerr << "Set Road: " << x << " " << y << '\n';
}

int main()
{
    int N;
    cin >> N;
    run(N);

}

#endif

Compilation message

icc.cpp: In function 'void newRoad(int, int)':
icc.cpp:42: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:66: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:102: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 solveComp2(std::vector<int>, std::vector<int>)':
icc.cpp:120:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = mij; i < A.size(); i++) X[1].push_back(A[i]), Y[1].push_back(B[i]);
                      ~~^~~~~~~~~~
icc.cpp: In function 'void findRoad()':
icc.cpp:130:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int b = 0; (1 << b) < comp.size(); b++)
                    ~~~~~~~~~^~~~~~~~~~~~~
icc.cpp:133:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < comp.size(); i++)
                        ~~^~~~~~~~~~~~~
icc.cpp:140:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < comp.size(); i++)
                    ~~^~~~~~~~~~~~~
icc.cpp:143:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i < j && j < comp.size())
                     ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Ok! 110 queries used.
2 Correct 9 ms 504 KB Ok! 108 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 676 KB Ok! 611 queries used.
2 Correct 40 ms 676 KB Ok! 501 queries used.
3 Correct 43 ms 676 KB Ok! 538 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 788 KB Ok! 1515 queries used.
2 Correct 118 ms 932 KB Ok! 1220 queries used.
3 Correct 139 ms 932 KB Ok! 1539 queries used.
4 Correct 147 ms 932 KB Ok! 1509 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 932 KB Ok! 1515 queries used.
2 Correct 148 ms 932 KB Ok! 1507 queries used.
3 Correct 138 ms 932 KB Ok! 1488 queries used.
4 Correct 153 ms 932 KB Ok! 1536 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 932 KB Ok! 1456 queries used.
2 Correct 138 ms 1024 KB Ok! 1506 queries used.
3 Correct 130 ms 1024 KB Ok! 1360 queries used.
4 Correct 139 ms 1024 KB Ok! 1519 queries used.
5 Correct 141 ms 1024 KB Ok! 1528 queries used.
6 Correct 141 ms 1024 KB Ok! 1523 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 1024 KB Ok! 1454 queries used.
2 Correct 131 ms 1024 KB Ok! 1251 queries used.