제출 #44723

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44723		bogdan10bos	ICC (CEOI16_icc)	C++14	61 / 100	238 ms	1188 KiB

icc

#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();
}

컴파일 시 표준 에러 (stderr) 메시지

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