8882022-01-25 10:39:57Halasz EszterÜzletlánccpp11Wrong answer 4/40119ms15988 KiB
#include <iostream>
//#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

//ifstream cin("uzletlanc.in");
//ofstream cout("uzletlanc.out");

struct adat
{
    int alep,blep,lat,p;
    bool lep;
    vector<int>sz;
};
vector<adat>x;

deque<int>y;

vector<int>v;
vector<string >meg;

int n,m,a,b,i,p,q,csp,db,dba,dbb;

int has(adat a, adat b)
{
    if(a.blep>b.blep) return 1;
    else return 0;
}
int main()
{
    cin>>n>>m>>a>>b;
    x.resize(n+1);
    for(i=1;i<=m;++i)
    {
        cin>>p>>q;
        x[p].sz.push_back(q);
        x[q].sz.push_back(p);
    }

    y.push_back(a);
    x[a].lat=1;
    while(!y.empty())
    {
        csp=y.front();
        y.pop_front();
        for(auto e:x[csp].sz)
        {
            if(x[e].lat==0)
            {
                x[e].lat=1;
                x[e].alep=x[csp].alep+1;
                y.push_back(e);
            }
            else x[e].alep=min(x[e].alep,x[csp].alep+1);
        }
    }

    for(i=1;i<=n;++i)
    {
        x[i].lat=0;
        x[i].p=i;
    }

    y.push_back(b);
    x[b].lat=1;
    while(!y.empty())
    {
        csp=y.front();
        y.pop_front();
        for(auto e:x[csp].sz)
        {
            if(x[e].lat==0)
            {
                x[e].lat=1;
                x[e].blep=x[csp].blep+1;
                y.push_back(e);
            }
            else x[e].blep=min(x[e].blep,x[csp].blep+1);
        }
    }

   x[b].alep=0;
    x[a].blep=0;
    //for(i=1;i<=n;++i)
      //  cout<<i<<": "<<x[i].alep<<" "<<x[i].blep<<"\n";

    v.resize(n+1);
    for(i=1;i<=n;++i)
        v[i]=x[i].alep;

         meg.resize(n+1);
    meg[a]='A';
    meg[b]='B';
    dba=n/2-1;
    dbb=dba;


   sort(x.begin()+1,x.end(),has);

    for(i=1;i<=n;++i)
    {
        if(x[i].p!=a && x[i].p!=b)
        {
            if(x[i].blep>v[x[i].p] && dba!=0)
            {
                meg[x[i].p]='A';
                db+=v[x[i].p];
                dba--;
            }
            else
            {
                meg[x[i].p]='B';
                db+=x[i].blep;
                dbb--;
            }
        }
    }
    cout<<db<<"\n";

    for(i=1;i<=n;++i) cout<<meg[i];



    return 0;
}
SubtaskSumTestVerdictTimeMemory
base4/40
1Accepted0/02ms1872 KiB
2Wrong answer0/02ms1920 KiB
3Accepted2/21ms1968 KiB
4Accepted2/21ms1972 KiB
5Wrong answer0/31ms1976 KiB
6Wrong answer0/31ms1992 KiB
7Wrong answer0/21ms1992 KiB
8Wrong answer0/21ms2004 KiB
9Wrong answer0/31ms2008 KiB
10Wrong answer0/31ms2012 KiB
11Wrong answer0/29ms3072 KiB
12Wrong answer0/212ms3416 KiB
13Wrong answer0/354ms5888 KiB
14Wrong answer0/38ms3948 KiB
15Wrong answer0/2107ms13028 KiB
16Wrong answer0/2118ms14244 KiB
17Wrong answer0/3111ms14048 KiB
18Wrong answer0/3119ms15988 KiB