Submission #584115

#	Time	Username	Problem	Language	Result	Execution time	Memory
584115		azberjibiou	Split the Attractions (IOI19_split)	C++17	100 / 100	355 ms	60260 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;
bool do_assert;
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 Chk3[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;
    Chk3[now]=true;
    for(int nxt : v[now])   if(!Chk3[nxt] && res[nxt]==typ)
    {
        cnt=dfs3(nxt, cnt, typ);
    }
    return cnt;
}
void assert3()
{
    for(int i=0;i<N;i++)    assert(res[i]!=0);
}
void make3()
///color 3 when res is made out of 1 and 2
{
    init_uf();
    for(pii ele : E)    if(res[ele.fir]==res[ele.sec])  onion(ele.fir, ele.sec);
    int root1, root2;
    for(int i=0;i<N;i++)
    {
        if(res[i]==1)   root1=i;
        else    root2=i;
    }
    if(do_assert)
    {
        for(int i=0;i<N;i++)
        {
            if(res[i]==1)   assert(findpar(i)==findpar(root1));
            else    assert(findpar(i)==findpar(root2));
        }
    }


    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, now);
        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-A)
    {
        int ncol=(comp[0].sec<=N-B ? 1 : 2);
        if(comp[0].fir==pre)
        {
            
            int tmpcnt1=0;
            for(int nxt : child[now])
            {
                if(reach[nxt]>=disc[now])  color(nxt, now, 3-ncol);
                else    color(nxt, now, ncol);
            }
            color(pre, now, ncol);
            res[now]=3-ncol;
            assert3();
        }
        else
        {
            color(comp[0].fir, now, ncol);
            color(now, comp[0].fir, 3-ncol);
        }
        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);
        if(comp[0].fir!=pre)
        {
            for(int nxt : child[now])  if(reach[nxt]<disc[now]) dfs1(nxt, now, now);
        }
    }
    for(int nxt : child[now])   if(par[nxt]==nxt)   dfs2(nxt, now);
}
int cnt[mxN];   ///각 정점별 가중치
vector <int> new_v[mxN];    /// 2-connected graph에서 간선 저장
vector <pii> new_E;
bool new_Chk[mxN];
int new_par[mxN];
int new_0;
vector <int> new_child[mxN];
int new_dep[mxN];   ///depth for dividing back edge
int new_deg[mxN];
vector<vector<int>> ear;
vector <int> cont[mxN];
void dfs4(int now)
{
    new_Chk[now]=true;
    for(int nxt : new_v[now])   if(!new_Chk[nxt])
    {
        new_child[now].push_back(nxt);
        new_par[nxt]=now;
        new_dep[nxt]=new_dep[now]+1;
        dfs4(nxt);
    }
}
typedef struct cmp1{
    bool operator()(pii a, pii b)
    {
        int p=min(new_dep[a.fir], new_dep[a.sec]), q=min(new_dep[b.fir], new_dep[b.sec]);
        return p<q;
    }
}cmp1;
bool path_Chk[2*mxN];
vector <int> walk;
void f(int idx, int st)
{
    path_Chk[idx]=true;
    if(ear[idx][0]!=st) reverse(ear[idx].begin(), ear[idx].end());
    for(int i=1;i+1<ear[idx].size();i++)
    {
        walk.push_back(ear[idx][i]);
        for(int ele : cont[ear[idx][i]])    if(!path_Chk[ele])   f(ele, ear[idx][i]);
    }
}
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=abc[0].fir;   B=abc[1].fir;   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 x, int y){return sub[x]>sub[y];});
        if(sub[child[0][0]]<A)  return res;
        else if(sub[child[0][0]]<=N-A)
        {
            int ncol=(sub[child[0][0]]<=N-B ? 1 : 2);
            color(child[0][0], 0, ncol);
            color(0, child[0][0], 3-ncol);
            make3();
            return res;
        }
        else
        {
            for(int i=1;i<child[0].size();i++)  dfs1(child[0][i], 0, 0);
        }
    }
    dfs2(0, -1);
    if(ok!=0)   return res;
    for(int i=0;i<N;i++)
    {
        cnt[findpar(i)]++;
    }
    for(pii ele : E)
    {
        int p=findpar(ele.fir), q=findpar(ele.sec);
        if(p==q)    continue;
        new_v[p].push_back(q);
        new_v[q].push_back(p);
        new_E.emplace_back(p, q);
    }
    for(int i=0;i<N;i++)    if(new_v[i].size())
    {
        sort(new_v[i].begin(), new_v[i].end());
        new_v[i].erase(unique(new_v[i].begin(), new_v[i].end()), new_v[i].end());
    }
    for(int i=0;i<N;i++)    new_deg[i]=new_v[i].size();
    new_0=findpar(0);
    new_par[new_0]=-1;
    dfs4(new_0);
    priority_queue <pii, vector<pii>, cmp1> pq;
    for(pii ele : new_E)
    {
        if(new_dep[ele.fir]>new_dep[ele.sec])   swap(ele.fir, ele.sec);
        if(new_dep[ele.fir]!=new_dep[ele.sec]-1)
        {
            pq.push(ele);
        }
    }
    while(!pq.empty())
    {
        pii now=pq.top();
        pq.pop();
        vector <int> path;
        path.push_back(now.fir);
        path.push_back(now.sec);
        new_deg[now.fir]--; new_deg[now.sec]--;
        int pos=now.sec;
        while(new_deg[pos]==1)
        {
            new_deg[pos]--;
            pos=new_par[pos];
            new_deg[pos]--;
            path.push_back(pos);

        }
        ear.push_back(path);
    }
    /*printf("ear");
    for(vector <int> ve : ear)
    {
        for(int ele : ve)   printf("%d ", ele);
        printf("\n");
    }*/
    for(int i=0;i+1<ear.size();i++)
    {
        cont[ear[i][0]].push_back(i);
        cont[ear[i].back()].push_back(i);
    }
    cont[ear[ear.size()-1][0]].push_back(ear.size()-1);
    for(int i=0;i<N;i++)    if(cont[i].size())  sort(cont[i].begin(), cont[i].end());
    int wstart=ear[ear.size()-1][0];
    walk.push_back(wstart);
    for(int ele : cont[wstart]) f(ele, wstart);
    /*printf("walk\n");
    for(int ele : walk) printf("%d\n", ele);*/
    int sum=0;
    for(int i=0;i<walk.size();i++)
    {
        sum+=cnt[walk[i]];
        if(sum>=B)
        {
            for(int j=0;j<=i;j++)   res[walk[j]]=2;
            for(int j=i+1;j<walk.size();j++)    res[walk[j]]=1;
            break;
        }
        else if(sum>=A)
        {
            for(int j=0;j<=i;j++)   res[walk[j]]=1;
            for(int j=i+1;j<walk.size();j++)    res[walk[j]]=2;
            break;
        }
    }
    for(int i=0;i<N;i++)    if(findpar(i)!=i)   res[i]=res[findpar(i)];
    make3();
	return res;
}

/*15 18
5 5 6
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 0
0 8
8 9
9 10
10 3
9 11
11 6
0 12
12 13
12 14
13 14*/

Compilation message (stderr)

split.cpp: In function 'void dfs2(int, int)':
split.cpp:108:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(int i=0;i<child[now].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~
split.cpp:124:17: warning: unused variable 'tmpcnt1' [-Wunused-variable]
  124 |             int tmpcnt1=0;
      |                 ^~~~~~~
split.cpp:144: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]
  144 |         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 'void f(int, int)':
split.cpp:187:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |     for(int i=1;i+1<ear[idx].size();i++)
      |                 ~~~^~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:202:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |  for(int i=0;i<p.size();i++)
      |              ~^~~~~~~~~
split.cpp:225:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |             for(int i=1;i<child[0].size();i++)  dfs1(child[0][i], 0, 0);
      |                         ~^~~~~~~~~~~~~~~~
split.cpp:285:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  285 |     for(int i=0;i+1<ear.size();i++)
      |                 ~~~^~~~~~~~~~~
split.cpp:298:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  298 |     for(int i=0;i<walk.size();i++)
      |                 ~^~~~~~~~~~~~
split.cpp:304:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  304 |             for(int j=i+1;j<walk.size();j++)    res[walk[j]]=1;
      |                           ~^~~~~~~~~~~~
split.cpp:310:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  310 |             for(int j=i+1;j<walk.size();j++)    res[walk[j]]=2;
      |                           ~^~~~~~~~~~~~
split.cpp: In function 'void make3()':
split.cpp:93:9: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |     dfs3(root2, B, 2);
      |     ~~~~^~~~~~~~~~~~~
split.cpp:92:9: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |     dfs3(root1, A, 1);
      |     ~~~~^~~~~~~~~~~~~

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