제출 #1292491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292491		MMihalev	Split the Attractions (IOI19_split)	C++20	컴파일 에러	0 ms	0 KiB

split

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include "split.h"
using namespace std;
const int MAX_N=1e5+5;
vector<int>g[MAX_N];
int col[MAX_N];
int deg[MAX_N];
int A,B;
int whA,whB;
int parent[MAX_N];
int sz[MAX_N];
void dfs(int u,int par)
{
    //sz[u]=1;
    for(int v:g[u])
    {
        if(v==par)continue;
        //deg[u]++;
        //deg[v]++;
        //parent[v]=u;
        dfs(v,u);
        //sz[u]+=sz[v];
    }
}
int ban=-1;
void colour(int u,int color)
{
    if(u==-1)while(1);
    col[u]=color;
    for(int v:g[u])
    {
        if(col[v]==color or v==ban)continue;
        colour(v,color);
    }
}
vector<int>ans;
vector<pair<int,int>>shit;
int N;
void solve()
{
    queue<int>bfs;
    int cntwhA=0;
    for(int i=0;i<N;i++)
    {
        if(col[i]==whA)
        {
            cntwhA++;
            if(deg[i]==1)bfs.push(i);
        }
    }
    int toremove=cntwhA-A;
    while(bfs.size()>0 && toremove>0)
    {
        int u=bfs.front();
        bfs.pop();
        toremove--;
        col[u]=shit[2].second;

        for(int v:g[u])
        {
            if(col[v]==whA)
            {
                deg[v]--;
                if(deg[v]==1)bfs.push(v);
            }
        }
    }

    while(bfs.size()>0)bfs.pop();
    int cntwhB=0;
    for(int i=0;i<N;i++)
    {
        if(col[i]==whB)
        {
            cntwhB++;
            if(deg[i]==1)bfs.push(i);
        }
    }
    toremove=cntwhB-B;
    while(bfs.size()>0 && toremove>0)
    {
        int u=bfs.front();
        bfs.pop();
        toremove--;
        col[u]=shit[2].second;

        for(int v:g[u])
        {
            if(col[v]==whB)
            {
                deg[v]--;
                if(deg[v]==1)bfs.push(v);
            }
        }
    }
    //B

    for(int i=0;i<N;i++)ans[i]=col[i];
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
    N=n;

    ans.resize(n);

    for(int i=0;i<n;i++)
    {
        col[i]=0;
        g[i].clear();
        deg[i]=0;
    }
    shit.clear();
    shit.push_back({a,1});
    shit.push_back({b,2});
    shit.push_back({c,3});
    sort(shit.begin(),shit.end());

    A=shit[0].first;whA=shit[0].second;
    B=shit[1].first;whB=shit[1].second;

    for(int i=0;i<min(100,p.size());i++)
    {
        g[p[i]].push_back(q[i]);
        g[q[i]].push_back(p[i]);
    }

    parent[0]=-1;
    dfs(0,-1);

    return ans;

    vector<pair<int,int>>subtrees;
    for(int i=0;i<n;i++)
    {
        subtrees.clear();
        int all=1;
        for(int u:g[i])
        {
            if(u==parent[i])continue;
            subtrees.push_back({sz[u],u});
            all+=sz[u];
        }
        if(i>0)subtrees.push_back({n-all,parent[i]});
        sort(subtrees.begin(),subtrees.end());

        int firstA=-1,firstB=-1;
        for(auto [s,u]:subtrees)
        {
            if(s>=A && firstA==-1)
            {
                firstA=u;
            }
            if(s>=B && firstB==-1)
            {
                firstB=u;
            }
        }

        if(firstA==-1)continue;

        if(n-sz[firstA]>=B)
        {
            colour(0,whB);
            ban=i;
            colour(firstA,whA);
            solve();
            return ans;
        }
        else if(firstB!=-1 && n-sz[firstB]>=A)
        {
            colour(0,whA);
            ban=i;
            colour(firstB,whB);
            solve();
            return ans;
        }
        else continue;
    }

    return ans;
}

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

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:124:22: error: no matching function for call to 'min(int, std::vector<int>::size_type)'
  124 |     for(int i=0;i<min(100,p.size());i++)
      |                   ~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/13/string:51,
                 from /usr/include/c++/13/bits/locale_classes.h:40,
                 from /usr/include/c++/13/bits/ios_base.h:41,
                 from /usr/include/c++/13/ios:44,
                 from /usr/include/c++/13/ostream:40,
                 from /usr/include/c++/13/iostream:41,
                 from split.cpp:1:
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
split.cpp:124:22: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::vector<int>::size_type' {aka 'long unsigned int'})
  124 |     for(int i=0;i<min(100,p.size());i++)
      |                   ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note:   template argument deduction/substitution failed:
split.cpp:124:22: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::vector<int>::size_type' {aka 'long unsigned int'})
  124 |     for(int i=0;i<min(100,p.size());i++)
      |                   ~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from split.cpp:3:
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5775 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note:   template argument deduction/substitution failed:
split.cpp:124:22: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  124 |     for(int i=0;i<min(100,p.size());i++)
      |                   ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5785 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note:   template argument deduction/substitution failed:
split.cpp:124:22: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  124 |     for(int i=0;i<min(100,p.size());i++)
      |                   ~~~^~~~~~~~~~~~~~