제출 #583966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
583966		azberjibiou	Split the Attractions (IOI19_split)	C++17	0 / 100	97 ms	21364 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define fir first
#define sec second
#define pii pair<int, int>
const int mxN=100010;

using namespace std;
int N, A, B, C;
vector <pii> abc;   ///크기순 정렬
vector <int> res;
vector <int> v[mxN];    ///간선
vector <pii> E; ///간선
int disc[mxN], tim, reach[mxN]; ///articulation point 찾을 때 사용
bool art[mxN];  ///cut vertex
vector <int> child[mxN], treev[mxN];    ///spanning tree while dfs
int sub[mxN];   ///size of subtree
int par[mxN];   ///uf
void init_uf(){for(int i=0;i<N;i++)   par[i]=i;}
int findpar(int a){return (par[a]==a ? a : par[a]=findpar(par[a]));}
void onion(int a, int b){int p=findpar(a), q=findpar(b); par[p]=q;}
void dfs0(int now)
{
    disc[now]=++tim;
    reach[now]=tim;
    sub[now]=1;
    for(int nxt : v[now])
    {
        if(!disc[nxt])
        {
            child[now].push_back(nxt);
            treev[now].push_back(nxt);  treev[nxt].push_back(now);
            dfs0(nxt);
            if(reach[nxt]>=disc[now] && now!=0) art[now]=true;
            reach[now]=min(reach[now], reach[nxt]);
            sub[now]+=sub[nxt];
        }
        else
        {
            reach[now]=min(reach[now], disc[nxt]);
        }
    }
}
void color(int now, int pre, int col)   ///colors subtree of now which its parent is pre with color col
{
    res[now]=col;
    for(int nxt : treev[now])   if(nxt!=pre)    color(nxt, now, col);
}
void dfs1(int now, int pre, int parent)  ///merge child of now to parent
{
    par[now]=parent;
    for(int nxt : treev[now])   if(par[nxt]==nxt && nxt!=pre)   dfs1(nxt, now, parent);
}
bool Chk[mxN];
int dfs3(int now, int cnt, int typ)
///color 3 to make cnt[1]=A, cnt[2]=B
{
    if(cnt>0)  cnt--;
    else    res[now]=3;
    Chk[now]=true;
    for(int nxt : v[now])   if(!Chk[nxt] && res[nxt]==typ)
    {
        cnt=dfs3(nxt, cnt, typ);
    }
    return cnt;
}
void make3()
///color 3 when res is made out of 1 and 2
{
    int root1, root2;
    for(int i=0;i<N;i++)
    {
        if(res[i]==1)   root1=i;
        else    root2=i;
    }
    dfs3(root1, A, 1);
    dfs3(root2, B, 2);
    for(int i=0;i<N;i++)    res[i]=abc[res[i]-1].sec;
}
int ok;
void dfs2(int now, int pre)
///merge adjacent component from articulation point
{
    if(ok!=0) return;
    if(now==0 || !art[now])
    {
        for(int nxt : child[now])   if(par[nxt]==nxt)   dfs2(nxt, 0);
        return;
    }
    vector <pii> comp;
    comp.emplace_back(pre, N-sub[now]);
    for(int i=0;i<child[now].size();i++)
    {
        if(reach[child[now][i]]>=disc[now]) comp.emplace_back(child[now][i], sub[child[now][i]]);
        else    comp[0].sec+=sub[child[now][i]];
    }
    sort(comp.begin(), comp.end(), [](pii a, pii b){return a.sec>b.sec;});
    if(comp[0].sec<A)
    {
        ok=-1;   return;
    }
    else if(comp[0].sec<=N-B)
    {
        if(comp[0].fir==pre)
        {
            for(int nxt : child[now])
            {
                if(reach[nxt]>=reach[now])  color(nxt, now, 1);
                else    color(nxt, now, 2);
            }
            color(pre, now, 1);
            res[now]=2;
        }
        else
        {
            color(comp[0].fir, now, 1);
            color(now, comp[0].fir, 2);
        }
        make3();
        ok=1;   return;
    }
    else
    {
        for(int i=1;i<comp.size();i++)  if(par[comp[i].fir]==comp[i].fir)   dfs1(comp[i].fir, now, now);
    }
    for(int nxt : child[now])   if(par[nxt]==nxt)   dfs2(nxt, 0);
}

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

	abc.emplace_back(a, 1);
	abc.emplace_back(b, 2);
	abc.emplace_back(c, 3);
	sort(abc.begin(), abc.end());
	A=a=abc[0].fir;   B=b=abc[1].fir;   C=c=abc[2].fir;
	for(int i=0;i<p.size();i++)
    {
        v[p[i]].push_back(q[i]);
        v[q[i]].push_back(p[i]);
        E.emplace_back(q[i], p[i]);
    }
    dfs0(0);
    init_uf();
    if(child[0].size()>=2)  art[0]=true;
    if(art[0])
    {
        sort(child[0].begin(), child[0].end(), [](int a, int b){return sub[a]>sub[b];});
        if(sub[child[0][0]]<a)  return res;
        if(sub[child[0][0]]>=a && sub[child[0][0]]<=N-b)
        {
            color(child[0][0], 0, 1);
            color(0, child[0][0], 2);
            make3();
            return res;
        }
        else
        {
            for(int i=1;i<child[0].size();i++)  dfs1(child[0][i], 0, 0);
        }
    }
    dfs2(0, -1);
	return res;
}

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

split.cpp: In function 'void dfs2(int, int)':
split.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i=0;i<child[now].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~
split.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for(int i=1;i<comp.size();i++)  if(par[comp[i].fir]==comp[i].fir)   dfs1(comp[i].fir, now, now);
      |                     ~^~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:139:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |  for(int i=0;i<p.size();i++)
      |              ~^~~~~~~~~
split.cpp:161:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |             for(int i=1;i<child[0].size();i++)  dfs1(child[0][i], 0, 0);
      |                         ~^~~~~~~~~~~~~~~~
split.cpp: In function 'void make3()':
split.cpp:77:9: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |     dfs3(root2, B, 2);
      |     ~~~~^~~~~~~~~~~~~
split.cpp:76:9: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |     dfs3(root1, A, 1);
      |     ~~~~^~~~~~~~~~~~~

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