QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#787890#8544. Colorful Graph 2DepletedPrism#WA 117ms3840kbC++231.8kb2024-11-27 15:08:352024-11-27 15:08:35

Judging History

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

  • [2024-11-27 15:08:35]
  • 评测
  • 测评结果:WA
  • 用时:117ms
  • 内存:3840kb
  • [2024-11-27 15:08:35]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n; 
long long ha(int x,int y){
  return x%n*200003ll+y%n;
}
vector<int> G[N];
char c[2]={'R','B'};
int main(){
  int T;
  cin>>T;
  while(T--){
    // int n;
    cin>>n;
    int m;
    cin>>m;
    unordered_map<long long,char> mp;
    vector<int> ans(n,-1);
    for(int i=0;i<n;i++){
      G[i].clear();
    }
    for(int i=1;i<=m;i++){
      int x,y;
      cin>>x>>y;
      if(x>y){
        G[x].push_back(y+n);
        G[y].push_back(x);
      }else{
        G[x].push_back(y);
        G[y].push_back(x+n);
      }
    }
    for(int i=0;i<n;i++){
      G[i].push_back(i+1);
      G[i].push_back((i-1+n)%n);
      sort(G[i].begin(),G[i].end());
      // cout<<i<<endl;
      // for(auto t:G[i])cout<<t<<" ";cout<<endl;
    }
    ans[0]=0;
    queue<int> q;
    q.push(0);
    while(!q.empty()){
      int top=q.front();
      q.pop();
      int sz=G[top].size();
      int s=G[top][0];
      int t=G[top][sz-1];
      if(ans[s]>=0&&ans[t]>=0){
        continue;
      }else if(ans[s]>=0){
        int now=ans[s]^1;
        for(int i=1;i<sz;i++){
          int nx=G[top][i]%n;
          ans[nx]=now;
          now^=1;
          q.push(nx);
        }
      }else if(ans[t]>=0){
        int now=ans[t]^1;
        for(int i=sz-2;i>=0;i--){
          int nx=G[top][i]%n;
          ans[nx]=now;
          now^=1;
          q.push(nx);
        }
      }else{
        int now=0;
        for(int i=0;i<sz;i++){
          int nx=G[top][i]%n;
          ans[nx]=now;
          now^=1;
          q.push(nx);
        }
      }
    }
    for(int i=0;i<n;i++){
      if(ans[i]){
        cout<<'R';
      }else{
        cout<<'B';
      }
    }
    cout<<endl;
    
  }
    
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3640kb

input:

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

output:

BBR
RBBR
RBRRBR

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 117ms
memory: 3840kb

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:

RBRRRRBRB
BBR
RBRBB
RRRRBR
BRRRRRRRR
BBR
RBRRRBR
RBRRRRR
RBBR
BBRBBR
RBBRRB
RRRBRRR
RBBBRRRB
BBR
RBRBRRBR
RBBBRRRB
BBR
RBRRRRRRRR
RRRRRRRR
RRRRRRRRRR
RRRRRRRRRR
RBRRRRRRRR
BBR
BRRRBRR
RBBBRR
RBRRRRRR
BBRR
RBRRRRR
RRRRRRRRRR
RRRRRRR
RRRRRRRR
RBBBRR
RBRRBR
BBR
BBR
RRRRRRRRR
RRBRRRR
RBRRR
RRRRRRRRRR
RB...

result:

wrong answer cycle detected (test case 4)