oj.uz

Submission #44725

# Submission time Handle Problem Language Result Execution time Memory
44725 2018-04-05T14:02:05 Z bogdan10bos ICC (CEOI16_icc) C++14
0 / 100
 5 ms 636 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 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(i), B.push_back(j);
    }
    solveComp2(A, B);
}

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 solveComp2(std::vector<int>, std::vector<int>)':
icc.cpp:110: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:120:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int b = 0; (1 << b) < comp.size(); b++)
                    ~~~~~~~~~^~~~~~~~~~~~~
icc.cpp:123:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < comp.size(); i++)
                        ~~^~~~~~~~~~~~~
icc.cpp:130:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < comp.size(); i++)
                    ~~^~~~~~~~~~~~~
icc.cpp:133:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i < j && j < comp.size())
                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 616 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 616 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 636 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 636 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 636 KB Wrong road!
2 Halted 0 ms 0 KB -