QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#612264#8544. Colorful Graph 2swt2009TL 0ms11992kbC++141.9kb2024-10-05 09:55:102024-10-05 09:55:16

Judging History

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

  • [2024-10-05 09:55:16]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:11992kb
  • [2024-10-05 09:55:10]
  • 提交

answer

//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;  

#define int long long
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
#define lowbit(x) ((x)&(-x))

#define ppc __builtin_popcount

#define lc(p) ((p)<<1)
#define rc(p) ((p)<<1|1)

#define sqr(x) ((x)*(x))

// #define mod 1000000007
// #define mod 998244353
#define eps 1e-10

#define debug cout<<__LINE__<<" "<<__FUNCTION__<<"\n";
#define spa putchar(' ')
#define ero putchar('\n')

mt19937 rnd(time(0));

constexpr int N=1e6+10,inf=1e18;

inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline void write(int x){
	if(!x)putchar('0');
	if(x<0)x=-x,putchar('-');
	int cnt=0,a[30];
	while(x)a[++cnt]=x%10,x/=10;
	while(cnt--)putchar(a[cnt+1]+'0');
}

int nxt[N],a[N];

void solve(){
    int n=read(),m=read();
    if(!m){
        putchar('B');
        for(int i=2;i<=n;i++){
            putchar('R');
        }
        ero;
        return ;
    }
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++){
        nxt[i]=i-1;
    }
    for(int i=1;i<=m;i++){
        int u=read()+1,v=read()+1;
        if(u>v){
            swap(u,v);
        }
        nxt[v]=min(nxt[v],u);
    }
    // for(int i=1;i<=n;i++){
    //     cout<<f[i]<<" ";
    // }
    // cout<<"\n";
    for(int i=1;i<=n;i++){
        a[i]=a[nxt[i]]^1;
    }
    for(int i=1;i<=n;i++){
        // write(f[i]),spa;
        if(a[i]){
            putchar('R');
        }
        else{
            putchar('B');
        }
    }
    ero;
}

signed main(){
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
    int T=read();
    // int T=1;
    while(T--){
        solve();
    }
	return 0;
}

詳細信息

Test #1:

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

input:

3
3 0
4 1
1 3
6 3
0 2
2 4
4 0

output:

BRR
RBRR
RBBRBR

result:

ok ok (3 test cases)

Test #2:

score: -100
Time Limit Exceeded

input:

100000
9 6
2 0
4 6
3 6
0 6
0 7
2 6
3 0
5 2
2 4
2 0
6 3
1 5
4 1
2 4
9 6
3 1
6 4
8 1
3 6
1 6
8 6
3 0
7 4
3 0
4 0
6 4
3 1
7 4
5 1
5 0
3 1
1 4
4 1
1 3
6 3
2 4
4 0
2 0
6 3
3 0
1 3
5 3
7 4
0 5
2 5
5 1
3 5
8 5
4 1
5 1
5 0
1 3
5 7
3 0
8 5
0 2
4 6
0 6
0 3
4 0
8 5
5 1
1 4
5 0
3 1
5 7
3 0
10 7
0 2
9 2
5 8
3 9
...

output:

RBBRBRBBR
BRR
RBBRR
RBRBRR
RBRRBRRBR
BRR
RBRBBRR
RBRRRBR
RBRR
RBBRBR
RBRBRR
RBRBRBR
RBRRRBRR
BRR
RBBBBRBR
RBRRRBRR
BRR
RBBRBRBRRR
RBRRBRRR
RBRBRBRRRR
RBRBRBRBRR
RBBBRBBRBR
BRR
RBRBRBR
RBRRRR
RBBRRRRR
RBRR
RBBRBBR
RBRBRBBBBR
RBRBRBR
RBRBRBRR
RBRRRR
RBBRBR
BRR
BRR
RBRRRBBRR
RBRBBRR
RBRBR
RBRBRRBRRR
RB...

result: