Submission #1201094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201094		Kaang	Split the Attractions (IOI19_split)	C++20	Compilation error	0 ms	0 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using pll = pair<ll, ll>;
using vi = vector<int>;
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define sz(v) ((int)(v).size())
#define all(v) v.begin(), v.end()
using namespace std;
int dpt[100001],sz[100001],sp[100001],cnt,num[100001],p[100001],vst[100001],cnta,cntb,ta,tb,tp;
vector <int> v[100001],g[100001];
priority_queue <pii> pq;
vector <int> ans;
int dfs(int node,int par)
{
    cnt++;
    num[node]=cnt;
    sp[node]=cnt;
    sz[node]=1;
    p[node]=par;
    for(auto cur:v[node])
    {
        if(cur==par)
            continue;
        else if(!dpt[cur])
        {
            g[node].push_back(cur);
            dpt[cur]=dpt[node]+1;
            sp[node]=min(sp[node],dfs(cur,node));
            sz[node]+=sz[cur];
        }
        else
        {
            sp[node]=min(sp[node],num[cur]);
        }
    }
    return sp[node];
}
void fdfs(int node,int f)
{
    if(vst[node])
        return;
    else
    {
        vst[node]=f;
        for(auto cur:v[node])
            fdfs(cur,f);
    }
}
void adfs(int node,int f)
{
    if(vst[node]!=f||ans[node]!=0)
        return;
    else
    {
        if(cnta<ta&&vst[node]==f)
            ans[node]=f,cnta++;
        for(auto cur:g[node])
            adfs(cur,f);

    }
}
void bdfs(int node,int f)
{
    if(vst[node]!=f||ans[node]!=0)
        return;
    else
    {
        if(cntb<tb&&vst[node]==f)
            ans[node]=f,cntb++;
        for(auto cur:g[node])
            bdfs(cur,f);

    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    int m=p.size();
    ans.resize(n,0);
    if(a<=b&&b<=c)
        tp=1;
    else if(a<=c&&c<b)
        tp=2;
    else if(c<a&&a<=b)
        tp=3;
    else if(b<a&&a<=c)
        tp=4;
    else if(b<=c&&c<a)
        tp=5;
    else if(c<b&&b<a)
        tp=6;
    if(a>b)
        swap(a,b);
    if(a>c)
        swap(a,c);
    if(b>c)
        swap(b,c);
    ta=a,tb=b;
    for(int i=0;i<m;i++)
    {
        v[p[i]].push_back(q[i]);
        v[q[i]].push_back(p[i]);
    }
    dpt[0]=1;
    dfs(0,-1);
    int dt1=0,dt2=0;//dt1이면 해 존재, dt2면 해 구성 불가, 판별필요 없음
    for(int i=0;i<n;i++)
    {
        int mx1=0,mx2=0,lft=n-1;
        for(int cur:g[i])
        {
            if(sp[cur]>=num[i])
            {
                int szcur=sz[cur];
                lft-=szcur;
                if(szcur>=mx1)
                {
                    mx2=mx1;
                    mx1=szcur;
                }
                else if(szcur<mx1&&szcur>=mx2)
                {
                    mx2=szcur;
                }
            }

        }
        if(lft>=mx1)
        {
            mx2=mx1;
            mx1=lft;
        }
        else if(lft<mx1&&lft>=mx2)
        {
            mx2=lft;
        }
        if(mx1>=b&&n-mx1>=a)
        {
            dt1=1;
            vst[i]=1;
            if(lft==mx1)
            {
                fdfs(p[i],2);
                for(int cur:g[i])
                {
                    fdfs(cur,1);
                }
            }
            else
            {
                for(int cur:g[i])
                {
                    if(sz[cur]==mx1)
                    {
                        fdfs(cur,2);
                        break;
                    }
                }
                for(int cur:g[i])
                {
                    fdfs(cur,1);
                }
            }
            break;
        }
        else if(mx1>=b&&n-mx1<a)
            continue;
        else if(mx1<b&&mx2<a)
        {
            dt2=1;
            break;
        }
        else if(mx1<b&&mx2>=a)
        {
            dt1=1;
            vst[i]=2;
            if(lft==mx2)
            {
                fdfs(p[i],1);
                for(int cur:g[i])
                {
                    fdfs(cur,2);
                }
            }
            else
            {
                for(int cur:g[i])
                {
                    if(sz[cur]==mx2)
                    {
                        fdfs(cur,1);
                        break;
                    }
                }
                for(int cur:g[i])
                {
                    fdfs(cur,2);
                }
            }
            break;
        }
    }
    if(dt2)
        return ans;
    else if(dt1)
    {
        for(int i=0;i<n;i++)
        {
            if(vst[i]==1)
                adfs(i,1);
            else
                bdfs(i,2);
        }
        for(int i=0;i<n;i++)
        {
            if(ans[i]==0)
                ans[i]=3;
        }
        for(int i=0;i<n;i++)
        {
            if(tp==1)
                ans[i]=ans[i];
            else if(tp==2)
            {
                if(ans[i]==2)
                    ans[i]=3;
                else if(ans[i]==3)
                    ans[i]=2;
            }
            else if(tp==3)
            {
                if(ans[i]==1)
                    ans[i]=3;
                else if(ans[i]==2)
                    ans[i]=1;
                else if(ans[i]==3)
                    ans[i]=2;
            }
            else if(tp==4)
            {
                if(ans[i]==1)
                    ans[i]=2;
                else if(ans[i]==2)
                    ans[i]=1;
                else
                    ans[i]=3;
            }
            else if(tp==5)
            {
                if(ans[i]==1)
                    ans[i]=2;
                else if(ans[i]==2)
                    ans[i]=3;
                else
                    ans[i]=1;
            }
            else
            {
                if(ans[i]==1)
                    ans[i]=3;
                else if(ans[i]==2)
                    ans[i]=2;
                else
                    ans[i]=1;
            }
        }
        return ans;
    }
    else
    {
        int cura=0;
        pq.push({1,0});
        while(cura<a)
        {
            int node=pq.top().se;
            pq.pop();
            if(vst[node]==0)
            {
                vst[node]=1;
                cura++;
                int lft=n-1;
                for(int cur:g[node])
                {
                    if(sp[cur]>=num[node])
                    {
                        lft-=sz[node];
                        if(sz[cur]<a)
                        {
                            fdfs(cur,1);
                            cura+=sz[cur];
                        }
                    }
                }
                if(lft<a)
                {
                    fdfs(p[node],1);
                    cura+=lft;
                }
                for(int cur:v[node])
                {
                    if(vst[cur]==0)
                        pq.push({dpt[cur],cur});
                }
                if(vst[par[node]]==0)
                pq.push({dpt[p[node]],par[node]});
            }
        }
        for(int i=0;i<n;i++)
        {
            if(vst[i]!=1)
                vst[i]=2;
        }
        for(int i=0;i<n;i++)
        {
            if(vst[i]==1)
                adfs(i,1);
            else
                bdfs(i,2);
        }
        for(int i=0;i<n;i++)
        {
            if(ans[i]==0)
                ans[i]=3;
        }
        for(int i=0;i<n;i++)
        {
            if(tp==1)
                ans[i]=ans[i];
            else if(tp==2)
            {
                if(ans[i]==2)
                    ans[i]=3;
                else if(ans[i]==3)
                    ans[i]=2;
            }
            else if(tp==3)
            {
                if(ans[i]==1)
                    ans[i]=3;
                else if(ans[i]==2)
                    ans[i]=1;
                else if(ans[i]==3)
                    ans[i]=2;
            }
            else if(tp==4)
            {
                if(ans[i]==1)
                    ans[i]=2;
                else if(ans[i]==2)
                    ans[i]=1;
                else
                    ans[i]=3;
            }
            else if(tp==5)
            {
                if(ans[i]==1)
                    ans[i]=2;
                else if(ans[i]==2)
                    ans[i]=3;
                else
                    ans[i]=1;
            }
            else
            {
                if(ans[i]==1)
                    ans[i]=3;
                else if(ans[i]==2)
                    ans[i]=2;
                else
                    ans[i]=1;
            }
        }
        return ans;
    }
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:312:24: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
  312 |                 if(vst[par[node]]==0)
      |                        ^~~
      |                        __pstl::execution::v1::par
In file included from /usr/include/c++/11/pstl/glue_algorithm_defs.h:15,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from split.cpp:2:
/usr/include/c++/11/pstl/execution_defs.h:111:27: note: '__pstl::execution::v1::par' declared here
  111 | constexpr parallel_policy par{};
      |                           ^~~
split.cpp:313:24: error: no matching function for call to 'std::priority_queue<std::pair<int, int> >::push(<brace-enclosed initializer list>)'
  313 |                 pq.push({dpt[p[node]],par[node]});
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:86,
                 from split.cpp:2:
/usr/include/c++/11/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::pair<int, int>; _Sequence = std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >; _Compare = std::less<std::pair<int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::pair<int, int>]'
  640 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/11/bits/stl_queue.h:640:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<int, int>&'}
  640 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::pair<int, int>; _Sequence = std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >; _Compare = std::less<std::pair<int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::pair<int, int>]'
  648 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/11/bits/stl_queue.h:648:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
  648 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~