Submission #1045587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045587		boyliguanhan	Split the Attractions (IOI19_split)	C++17	100 / 100	147 ms	25684 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(0);
vector<int>adj[100100],adj2[100100];
bitset<100100>vis;
int sz[100100],THEONE,treep[100100],dep[100100],fardest[100100];
vector<int>ans;
int OK(int k,int a,int b,int c){
	sz[k]=1; vis[k]=1;
    fardest[k]=dep[k];
	for(auto i:adj[k]) if(!vis[i]){
		treep[i]=k; dep[i]=dep[k]+1;
		if(OK(i,a,b,c)) return 1;sz[k]+=sz[i];
        fardest[k]=min(fardest[k],fardest[i]);
	} else fardest[k]=min(fardest[k],dep[i]);
	if(a<=sz[k]&&sz[k]<=b+c)
		return THEONE=k,1;
    if(!THEONE&&sz[k]>a)
        THEONE=k;
	return 0;
}
void gendfstree(int n){
	vis[n]=1;
	for(auto i:adj[n])
		if(!vis[i]) gendfstree(i),
		adj2[n].push_back(i),
		adj2[i].push_back(n);
}
void docol(int n,int p,int &CC,int col){
	if(!CC) return;
	ans[n]=col,CC--;
	for(auto x:adj2[n])
		if(x-p)docol(x,n,CC,col);
}
void genans(int k,int a,int b,int c,int A,int B,int C){
	for(auto&i:ans)i=C;
	vis.reset();
	gendfstree(k);
	int n=a+b+c;
	if(sz[THEONE]>=b)
		swap(a,b),swap(A,B);
	docol(THEONE,treep[THEONE],a,A);
	docol(treep[THEONE],THEONE,b,B);
	assert(!a&&!b);
}
set<int> onesin;
void docol2(int n,int &CC,int col){
    if(!onesin.count(n))return;
    onesin.erase(n);
	if(!CC) return;
	ans[n]=col,CC--;
	for(auto x:adj[n])
		docol2(x,CC,col);
}
void addto(int n,set<int>&st){
    st.insert(n);
    for(auto i:adj[n])
        if(treep[i]==n)
            addto(i,st);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	ans.resize(n);
	vector<int> res;
	int m=p.size();
	for(int i=0;i<m;i++)
		adj[p[i]].push_back(q[i]),
		adj[q[i]].push_back(p[i]);
	int A=1,B=2,C=3;
	if(a>b)swap(a,b),swap(A,B);
	if(b>c)swap(b,c),swap(B,C);
	if(a>b)swap(a,b),swap(A,B);
    vis.reset();
    if(OK(0,a,b,c))
        genans(0,a,b,c,A,B,C);
    else {
        set<int>in2,in1;
        int sz1=sz[THEONE];
        addto(THEONE,in1);
        for(int i=0;i<n;i++)
            if(!in1.count(i))
                in2.insert(i);
        for(auto x:adj[THEONE])
            if(treep[x]==THEONE)
                if(fardest[x]<dep[THEONE]) {
                    addto(x,in2);
                    if(in2.size()>=a)break;
                }
        if(in2.size()<a)return ans;
        for(auto&i:ans)i=C;
        onesin=in2;
        for(auto i:in2)
            in1.erase(i);
        docol2(0,a,A);
        onesin=in1;
        docol2(THEONE,b,B);
    }
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'int OK(int, int, int, int)':
split.cpp:14:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   14 |   if(OK(i,a,b,c)) return 1;sz[k]+=sz[i];
      |   ^~
split.cpp:14:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   14 |   if(OK(i,a,b,c)) return 1;sz[k]+=sz[i];
      |                            ^~
split.cpp:19:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   19 |     if(!THEONE&&sz[k]>a)
      |     ^~
split.cpp:21:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   21 |  return 0;
      |  ^~~~~~
split.cpp: In function 'void genans(int, int, int, int, int, int, int)':
split.cpp:40:6: warning: unused variable 'n' [-Wunused-variable]
   40 |  int n=a+b+c;
      |      ^
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:87:34: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |                     if(in2.size()>=a)break;
      |                        ~~~~~~~~~~^~~
split.cpp:89:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |         if(in2.size()<a)return ans;
      |            ~~~~~~~~~~^~
split.cpp:78:13: warning: unused variable 'sz1' [-Wunused-variable]
   78 |         int sz1=sz[THEONE];
      |             ^~~

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