제출 #755630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
755630		Rafi22	Split the Attractions (IOI19_split)	C++14	18 / 100	163 ms	43152 KiB

split

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=200007;

bool odw[N];
int s[N];
vector<int>G[N];
set<int>G1[N];
vector<pair<int,int>>E;
vector<int>ans;
int id[N];

void dfs(int v)
{
    odw[v]=1;
    s[v]=1;
    for(auto u:G[v])
    {
        if(!odw[u])
        {
            G1[v].insert(u);
            G1[u].insert(v);
            dfs(u);
            s[v]+=s[u];
        }
        else E.pb({u,v});
    }
}

int C;

void get(int v,int o,int k)
{
    if(C==0) return;
    ans[v]=k;
    C--;
    for(auto u:G1[v])
    {
        if(u==o) continue;
        get(u,v,k);
    }
}

void mark(int v,int o,int k)
{
    id[v]=k;
    for(auto u:G1[v])
    {
        if(u==o) continue;
        mark(u,v,k);
    }
}

vector<int> find_split(int n,int a,int b,int c,vector<int>P,vector<int>Q)
{
    vector<pair<int,int>>V;
    V.pb({a,1});
    V.pb({b,2});
    V.pb({c,3});
    sort(all(V));
    int A=V[0].st,B=V[1].st;
    for(int i=0;i<sz(P);i++)
    {
        G[P[i]].pb(Q[i]);
        G[Q[i]].pb(P[i]);
    }
    dfs(0);
    ans.resize(n,0);
    int v=0;
    bool is=0;
    while(v!=-1)
    {
        int mx=0,p=-1;
        for(auto u:G1[v])
        {
            if(s[u]<s[v]&&s[u]>mx)
            {
                mx=s[u];
                p=u;
            }
        }
        if(mx<A) break;
        if(mx>=A&&n-mx>=B)
        {
            for(int i=0;i<n;i++) ans[i]=V[2].nd;
            C=A;
            get(p,v,V[0].nd);
            C=B;
            get(v,p,V[1].nd);
            is=1;
            break;
        }
        if(mx>=B&&n-mx>=A)
        {
            for(int i=0;i<n;i++) ans[i]=V[2].nd;
            C=B;
            get(p,v,V[1].nd);
            C=A;
            get(v,p,V[0].nd);
            is=1;
            break;
        }
        v=p;
    }
    if(is) return ans;
    int ile=n-s[v],X=-1;
    for(auto u:G1[v])
    {
        if(s[u]<s[v]) mark(u,v,u);
        else X=u;
    }
    if(X==-1) return ans;
    for(auto [x,y]:E)
    {
        if(id[x]<id[y]) swap(x,y);
        if(id[y]==0&&id[x]>0)
        {
            mark(id[x],v,0);
            ile+=s[id[x]];
            G1[v].erase(id[x]);
            G1[id[x]].erase(v);
            G1[x].insert(y);
            G1[y].insert(x);
            if(ile>=A&&n-ile>=B)
            {
                for(int i=0;i<n;i++) ans[i]=V[2].nd;
                C=A;
                get(X,v,V[0].nd);
                C=B;
                get(v,X,V[1].nd);
                break;
            }
            if(ile>=B&&n-ile>=A)
            {
                for(int i=0;i<n;i++) ans[i]=V[2].nd;
                C=B;
                get(X,v,V[1].nd);
                C=A;
                get(v,X,V[0].nd);
                break;
            }
        }
    }
    return ans;
}
/*
int main()
{
    vector<int>V=find_split(9, 4, 2, 3, {0, 0, 0, 0, 0, 0, 1, 3, 4, 5},{1, 2, 3, 4, 6, 8, 7, 7, 5, 6});
    for(auto x:V) cout<<x<<" ";
    cout<<endl;
    return 0;
}
*/

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

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:126:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  126 |     for(auto [x,y]:E)
      |              ^

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36