QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#577#356587#8130. Yet Another Balanced Coloring Problemucup-team134ucup-team134Success!2024-03-18 02:37:002024-03-18 02:37:01

详细

Extra Test:

Time Limit Exceeded

input:

1
100000 100000
100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 1000...

output:


result:


ID题目提交者结果用时内存语言文件大小提交时间测评时间
#356587#8130. Yet Another Balanced Coloring Problemucup-team134TL 72ms39416kbC++174.6kb2024-03-18 02:07:202024-03-18 02:37:37

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ld long double
#define li __int128

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<int D, typename T>struct vec : public vector<vec<D - 1, T>> {template<typename... Args>vec(int n = 0, Args... args) : vector<vec<D - 1, T>>(n, vec<D - 1, T>(args...)) {}};
template<typename T>struct vec<1, T> : public vector<T> {vec(int n = 0, T val = T()) : vector<T>(n, val) {}};
template<class T1,class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const deque<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
int ri(){int x;scanf("%i",&x);return x;}
void rd(int&x){scanf("%i",&x);}
void rd(long long&x){scanf("%lld",&x);}
void rd(double&x){scanf("%lf",&x);}
void rd(long double&x){scanf("%Lf",&x);}
void rd(string&x){cin>>x;}
void rd(char*x){scanf("%s",x);}
template<typename T1,typename T2>void rd(pair<T1,T2>&x){rd(x.first);rd(x.second);}
template<typename T>void rd(vector<T>&x){for(T&p:x)rd(p);}
template<typename C,typename...T>void rd(C&a,T&...args){rd(a);rd(args...);}
//istream& operator>>(istream& is,__int128& a){string s;is>>s;a=0;int i=0;bool neg=false;if(s[0]=='-')neg=true,i++;for(;i<s.size();i++)a=a*10+s[i]-'0';if(neg)a*=-1;return is;}
//ostream& operator<<(ostream& os,__int128 a){bool neg=false;if(a<0)neg=true,a*=-1;ll high=(a/(__int128)1e18);ll low=(a-(__int128)1e18*high);string res;if(neg)res+='-';if(high>0){res+=to_string(high);string temp=to_string(low);res+=string(18-temp.size(),'0');res+=temp;}else res+=to_string(low);os<<res;return os;}

const int N=2e5+5;
vector<vector<int>> graf(N);
vector<vector<pair<int,int>>> graf2(N);
vector<pair<int,int>> eds;
vector<bool> done(N);
vector<bool> ans(N);
int n,m,k;
int dfs(int tr,int par){
	if(tr<k){
		eds.pb({tr,par});
		return 1;
	}
	int cnt=0;
	for(auto p:graf[tr]){
		cnt+=dfs(p,tr);
	}
	if(par!=tr)
	if(cnt&1)eds.pb({tr,par});
	return cnt;
}
void dfs2(int tr,int par){
	if(tr<k){
		ans[tr]=par<n;
	}
	for(auto p:graf2[tr]){
		if(done[p.s])continue;
		done[p.s]=1;
		dfs2(p.f,tr);
	}
}
void test(){
	scanf("%i %i",&n,&m);
	for(int i=0;i<n+m;i++)graf[i].clear(),graf2[i].clear();
	eds.clear();
	for(int i=0;i<n-1;i++){
		int p;
		scanf("%i",&p);
		p--;
		graf[p].pb(i);
	}
	for(int i=0;i<n;i++){
		if(sz(graf[i])!=0||i==n-1){
			k=i;
			break;
		}
	}
	for(int i=0;i<m-1;i++){
		int p;
		scanf("%i",&p);
		p--;
		p+=n;
		int ind=i;
		if(ind>=k)ind+=n;
		graf[p].pb(ind);
	}
	dfs(n-1,n-1);
	dfs(n+m-1,n+m-1);
	if(k%2==1){
		eds.pb({n-1,n+m-1});
	}
	//cout << eds << endl;
	for(int i=0;i<sz(eds);i++){
		done[i]=0;
		int a=eds[i].f,b=eds[i].s;
		graf2[a].pb({b,i});
		graf2[b].pb({a,i});
	}
	for(int i=k;i<n+m;i++)
		dfs2(i,i);
	for(int i=0;i<k;i++){
		if(ans[i])printf("R");
		else printf("B");
	}
	printf("\n");
}
int main()
{
	int t;
	scanf("%i",&t);
	while(t--)test();
	return 0;
}