892021-01-10 21:18:18kris01Üzletlánccpp14Accepted 40/4046ms10204 KiB
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define mp make_pair
vector < vector <int> > Adj;
int INF = INT_MAX;

void BFS(int start,vector <int> &dist) {
  dist[start] = 0;
  queue <int> Q;
  Q.push(start);
  while (!Q.empty()) {
   int v = Q.front();
   Q.pop();
   for (int x : Adj[v]) {
    if (dist[x] > dist[v] + 1) {
     dist[x] = dist[v] + 1;
     Q.push(x);
    }
   }
  }
}

int main() {
	ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n,m;
  cin >> n >> m;
  int a,b;
  cin >> a >> b;
  Adj.resize(n+1);
  for (int i = 0;i < m;i++) {
    int u,v;
    cin >> v >> u;
    Adj[u].push_back(v);
    Adj[v].push_back(u);
  }
  vector <int> DistA(n+1,INF);
  vector <int> DistB(n+1,INF);
  BFS(a,DistA);
  BFS(b,DistB);
  vector <pair <int,int> > For_Sorting(n,{-1,-1}); 
  for (int i = 1;i <= n;i++) {
    int val = DistA[i] - DistB[i];
    For_Sorting[i-1] = mp(val,i);
  }
  sort(For_Sorting.begin(),For_Sorting.end());
  vector <int> A_Source;
  vector <int> B_Source;
  for (int i = 0;i < n/2;i++) {
    A_Source.push_back(For_Sorting[i].second);
  }
  for (int i = n/2;i < n;i++) {
    B_Source.push_back(For_Sorting[i].second);
  }
  int sum = 0;
  vector <int> Sol(n+1);
  for (int x : A_Source) {
    Sol[x] = 0;
    sum = sum + DistA[x];
  }
  for (int x : B_Source) {
    Sol[x] = 1;
    sum = sum + DistB[x];
  }
  cout << sum << endl;
  for (int i = 1;i <= n;i++) {
    if (Sol[i] == 0) {
      cout << 'A';
    } else {
      cout << 'B';
    }
  }
	return 0;
}
SubtaskSumTestVerdictTimeMemory
base40/40
1Accepted0/02ms1756 KiB
2Accepted0/02ms1876 KiB
3Accepted2/21ms1848 KiB
4Accepted2/21ms1852 KiB
5Accepted3/31ms1860 KiB
6Accepted3/31ms1892 KiB
7Accepted2/21ms1884 KiB
8Accepted2/21ms1888 KiB
9Accepted3/31ms1904 KiB
10Accepted3/32ms1896 KiB
11Accepted2/24ms2832 KiB
12Accepted2/26ms2940 KiB
13Accepted3/329ms5664 KiB
14Accepted3/34ms3612 KiB
15Accepted2/243ms9588 KiB
16Accepted2/246ms9840 KiB
17Accepted3/329ms9264 KiB
18Accepted3/346ms10204 KiB