oj.uz

답안 #577133

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
577133 2022-06-14T07:21:29 Z andrei_boaca One-Way Streets (CEOI17_oneway) C++14
0 / 100
 2 ms 2644 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int n,m,p;
pii keep[100005];
pii edge[100005],sol[100005];
vector<pii> muchii[100005];
int topar[100005];
int par[100005];
bool use[100005];
int nr1[100005],nr2[100005];
int niv[100005],nivmin[100005];
int root=1;
void dfs(int nod)
{
    use[nod]=1;
    if(nod==root)
        niv[nod]=1;
    nivmin[nod]=niv[nod];
    for(auto i:muchii[nod])
    {
        int a=i.first;
        int index=i.second;
        if(index==topar[nod])
            continue;
        if(!use[a])
        {
            niv[a]=niv[nod]+1;
            topar[a]=index;
            dfs(a);
            nr1[nod]+=nr1[a];
            nr2[nod]+=nr2[a];
            if(nivmin[a]<=niv[nod])
                sol[index]={-1,-1};
            else
            {
                if(nr1[a]>nr2[a])
                    sol[index]={a,nod};
                if(nr1[a]<nr2[a])
                    sol[index]={nod,a};
                if(nr1[a]==nr2[a])
                    sol[index]={-1,-1};
            }
            nivmin[nod]=min(nivmin[nod],nivmin[a]);
        }
        else
        {
            sol[index]={-1,-1};
            nivmin[nod]=min(nivmin[nod],niv[a]);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        edge[i]={a,b};
        muchii[a].push_back({b,i});
        muchii[b].push_back({a,i});
    }
    cin>>p;
    for(int i=1;i<=p;i++)
    {
        cin>>keep[i].first>>keep[i].second;
        int a=keep[i].first;
        int b=keep[i].second;
        nr1[a]++;
        nr2[b]++;
    }
    /*for(int i=1;i<=n;i++)
        if(!use[i])
        {
            root=i;
            dfs(root);
        }*/
    root=1;
    dfs(root);
    for(int i=1;i<=m;i++)
    {
        if(sol[i].first==-1)
            cout<<"B";
        else
            if(sol[i].first==edge[i].first)
                cout<<"R";
        else
            cout<<"L";
    }
    return 0;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -