Submission #44727

#	Time	Username	Problem	Language	Result	Execution time	Memory
44727		bogdan10bos	ICC (CEOI16_icc)	C++14	100 / 100	153 ms	1024 KiB

icc

#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 (stderr)

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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10