QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#788109#8544. Colorful Graph 2DepletedPrism#ML 1ms3512kbC++231.4kb2024-11-27 15:57:412024-11-27 15:57:43

Judging History

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

  • [2024-11-27 15:57:43]
  • 评测
  • 测评结果:ML
  • 用时:1ms
  • 内存:3512kb
  • [2024-11-27 15:57:41]
  • 提交

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> ans;
vector<int> G[N];
void dfs(int x){
  int sz=G[x].size();
  int pos=-1;
  for(int i=sz;i>=0;i--){
    if(ans[G[x][i]%n]<0){
      pos=i;
      break;
    }
  }
  // cout<<x<<" "<<pos<<endl;
  if(pos==-1)return ;
  
  int now=1;
  if(pos==sz-1){
    now=0;
  }else{
    now=ans[G[x][pos+1]%n]^1;
  }
  for(int i=pos;i>=0;i--){
    ans[G[x][i]%n]=now;
    now^=1;
  }
  for(int i=0;i<=pos;i++){
    dfs(G[x][i]%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;
    ans.clear();
    ans.resize(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);
      sort(G[i].begin(),G[i].end());
      // cout<<i<<endl;
      // for(auto t:G[i])cout<<t<<" ";cout<<endl;
    }
    ans[0]=0;
    dfs(0);
    for(int i=0;i<n;i++){
      cout<<c[ans[i]];
      // cout<<ans[i];
    }
    cout<<endl;
    
  }
    
  return 0;
}

详细

Test #1:

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

input:

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

output:

RBR
RBBR
RBRRBR

result:

ok ok (3 test cases)

Test #2:

score: -100
Memory 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:

RRBBBBRBR
RBR
BRBBR
RRBRBB
RRRBBBRBB
BRB
RBBRBBR
RRRBRBB

result: