QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#463782 | #8544. Colorful Graph 2 | PhantomThreshold# | WA | 215ms | 3660kb | C++20 | 1.2kb | 2024-07-05 14:17:27 | 2024-07-05 14:17:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
vector<int> deg(n+5);
vector<set<int>> G(n+5);
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
G[u].insert(v);
G[v].insert(u);
deg[u]++;deg[v]++;
}
for(int i=0;i<n;i++)
{
G[i].insert((i+1)%n);
G[(i+1)%n].insert(i);
deg[i]++;deg[(i+1)%n]++;
}
vector<int> pre(n+5);
queue<int> q;
for(int i=0;i<n;i++)
{
if(deg[i]==2)
q.push(i);
}
vector<int> ord;
while(not q.empty())
{
int u=q.front();q.pop();
ord.push_back(u);
if(deg[u]!=2)continue;
int x=*G[u].begin(),y=*next(G[u].begin());
for(auto z:G[u])
{
pre[u]=z;
deg[z]--;
G[z].erase(u);
}
if(not G[x].contains(y))
{
G[x].insert(y);
G[y].insert(x);
deg[x]++;deg[y]++;
}
if(deg[x]==2)
q.push(x);
if(deg[y]==2)
q.push(y);
}
string col(n+5,' ');
reverse(ord.begin(),ord.end());
for(auto z:ord)
{
if(not pre[z])
col[z]='R';
else
col[z]='R'+'B'-col[pre[z]];
}
for(int i=0;i<n;i++)
cout<<col[i];
cout<<"\n";
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
BRR BRBR RRBBRB
result:
ok ok (3 test cases)
Test #2:
score: 0
Accepted
time: 215ms
memory: 3660kb
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:
BBRBBBRBR BRR BBRBR RRBBRB RRRBBBRRB BRR RRRBRRB BRBRBRB BRBR RRBBRB RBBRRB BRBBBRB BRBRBRRB BRR RBRBRRBR BRBRBRRB BRR BRBBRRRRBR RBBRBBRB RRRRBBRBRB BRRBRRBRBR RRBRBRBRRB BRR RRBBRRB RRRBRB RBRBRBRB BRBR BRBRRBR BBRRRRBRBR RRRBBRB BRBBRRBR RRRBRB RRBBRB BRR BRR RBRBRRBRB RBBBRRB RBBRB BBBBBRBRBR RB...
result:
ok ok (100000 test cases)
Test #3:
score: -100
Wrong Answer
time: 152ms
memory: 3632kb
input:
100000 8 4 5 3 5 1 6 1 3 1 7 4 5 0 4 1 4 0 3 1 4 0 8 1 4 7 3 0 3 0 8 1 1 3 3 0 9 4 6 0 3 0 3 1 5 0 7 0 6 2 4 2 0 4 7 3 0 3 0 4 1 3 5 1 3 0 10 4 6 8 5 2 1 5 5 3 5 1 1 4 3 0 9 3 5 0 8 6 6 0 3 0 5 2 1 3 1 4 9 0 6 1 4 2 8 1 1 3 5 0 8 2 3 1 6 1 5 1 3 0 8 3 3 0 7 4 7 5 7 2 5 3 1 3 10 3 8 0 0 3 8 5 9 4 3 0...
output:
RRt tRB RBRBRBR BBRR BBBBRRBR BRR BRR RRBRRBRB BRR Rtt tRRB BBBBBRR RRBBRB R tRRB RRBRB RtR tBBRB BRRBR BRR RRBRBRtt BRR RRBRB BBBBBBBRR RRRBRB RRBRRBRB BBBRR RRRBRBRB RRBRB RRBR t RRRBBRB RRBRBRRBRB BRBRtRBBR RRBRBRBRB BBBBRR BBRRRBR BRR RRBRBRBRRB BRRBRB RRR t tRB BBRBR RRBRRRBRRB BBRBR BBR...
result:
wrong answer Token parameter [name=S] equals to "RRt", doesn't correspond to pattern "[BR]{1,200000}" (test case 1)