QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#356579#8130. Yet Another Balanced Coloring Problemucup-team134WA 14ms12696kbC++174.5kb2024-03-18 02:00:042024-03-18 02:00:05

Judging History

你现在查看的是最新测评结果

  • [2024-03-18 02:37:14]
  • hack成功,自动添加数据
  • (/hack/577)
  • [2024-03-18 02:00:05]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:12696kb
  • [2024-03-18 02:00:04]
  • 提交

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;
void dfs(int tr,int par){
	if(tr<k){
		eds.pb({tr,par});
		return;
	}
	int cnt=0;
	for(auto p:graf[tr]){
		cnt++;
		dfs(p,tr);
	}
	if(cnt&1)eds.pb({tr,par});
}
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&1){
		eds.pb({n-1,n+m-1});
	}
	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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 12696kb

input:

2
7 7
5 5 6 6 7 7
5 6 5 6 7 7
5 4
4 4 5 5
4 4 4

output:

RBBR
RBB

result:

ok ok (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 14ms
memory: 12548kb

input:

10000
6 6
5 5 5 5 6
5 6 6 6 6
9 6
7 9 7 7 6 8 9 9
6 6 6 6 6
9 8
9 9 8 7 7 8 8 9
7 7 8 7 7 7 8
6 10
4 5 5 6 6
4 6 5 7 8 9 8 9 10
6 9
6 6 6 6 6
6 9 7 8 8 9 9 9
8 9
8 6 6 7 6 7 8
7 9 7 6 7 8 9 9
9 8
6 7 7 5 8 8 8 9
7 5 6 5 8 7 8
8 7
6 6 5 5 6 7 8
5 7 6 6 7 7
9 9
8 9 8 8 8 8 9 9
9 9 8 8 9 9 8 9
9 8
8 8 ...

output:

RBRB
BBRRR
BRRRBB
RRB
RBRRB
BRRBB
BBRR
RBRB
RBBRBRR
RBBRBRR
RRB
RBRBRB
RRB
RBRBRBR
BRRRBB
RBRB
BRR
RRRBB
BRR
RRBBB
BBRRB
BRBR
RRBBR
BRB
RBRBR
RRBR
RBRBRB
BRRRBB
RBBR
BRRRBR
RRBRBB
RBRRB
RRBRBB
RBRBRB
BRRRBB
RBB
BRRB
BRR
RRB
RRRBB
RBBR
BRBRBB
RBR
RRBRR
BRR
RBRBRB
RRBRRB
RBR
RBRBRB
BBR
RBB
RBRB
RBRBR
...

result:

wrong answer charge of vertex 4 in tree 1 violates range (test case 11)