제출 #46974

#제출 시각아이디문제언어결과실행 시간메모리
46974dqhungdlOne-Way Streets (CEOI17_oneway)C++17
100 / 100
336 ms53416 KiB
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
int T,n,m,cnt=0,Time=0,Num[100005],Low[100005],In[100005],Out[100005],Pre[100005],h[100005],P[100005][20];
int sum1[100005],sum2[100005];
bool FEdge[100005];
vector<ii> Edge,gg[100005];
vector<int> g[100005];

void FindBridge(int u,int preid)
{
    Num[u]=Low[u]=++cnt;
    for(int i=0;i<gg[u].size();i++)
    {
        int v=gg[u][i].first;
        int id=gg[u][i].second;
        if(Num[v]==0)
        {
            FindBridge(v,id);
            Low[u]=min(Low[u],Low[v]);
            if(Low[v]>=Num[v])
                FEdge[id]=true;
        }
        else
        if(id!=preid)
            Low[u]=min(Low[u],Num[v]);
    }
}

void DFSComponent(int u,int kk)
{
    Pre[u]=kk;
    for(int i=0;i<gg[u].size();i++)
    {
        int v=gg[u][i].first;
        int id=gg[u][i].second;
        if(FEdge[id]==false&&Pre[v]==0)
            DFSComponent(v,kk);
    }
}

void DFSHigh(int u,int high)
{
    h[u]=high;
    In[u]=++Time;
    for(int i=0;i<g[u].size();i++)
        if(h[g[u][i]]==0)
        {
            P[g[u][i]][0]=u;
            DFSHigh(g[u][i],high+1);
        }
    Out[u]=Time;
}

int LCA(int u,int v)
{
    for(int k=17;k>=0;k--)
        if(h[P[u][k]]>=h[v])
            u=P[u][k];
        else
        if(h[P[v][k]]>=h[u])
            v=P[v][k];
    for(int k=17;k>=0;k--)
        if(P[u][k]!=P[v][k])
        {
            u=P[u][k];
            v=P[v][k];
        }
    while(u!=v)
    {
        u=P[u][0];
        v=P[v][0];
    }
    return u;
}

void SumDFS(int u,int root)
{
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=root)
        {
            SumDFS(g[u][i],u);
            sum1[u]+=sum1[g[u][i]];
            sum2[u]+=sum2[g[u][i]];
        }
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>n>>m;
    int u,v,Count=0;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        Edge.push_back(ii(u,v));
        gg[u].push_back(ii(v,i));
        gg[v].push_back(ii(u,i));
    }
    for(int i=1;i<=n;i++)
        if(Num[i]==0)
            FindBridge(i,0);
    for(int i=1;i<=n;i++)
        if(Pre[i]==0)
            DFSComponent(i,++Count);
    for(int i=0;i<Edge.size();i++)
    {
        int u=Pre[Edge[i].first];
        int v=Pre[Edge[i].second];
        if(u!=v)
        {
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }
    for(int i=1;i<=n;i++)
        if(h[i]==0)
            DFSHigh(i,1);
    for(int k=1;k<=17;k++)
        for(int i=1;i<=Count;i++)
            P[i][k]=P[P[i][k-1]][k-1];
    cin>>T;
    while(T--)
    {
        cin>>u>>v;
        u=Pre[u];
        v=Pre[v];
        int w=LCA(u,v);
        sum2[w]--;
        sum2[u]++;
        sum1[w]--;
        sum1[v]++;
    }
    SumDFS(1,1);
    for(int i=0;i<Edge.size();i++)
    {
        int u=Pre[Edge[i].first];
        int v=Pre[Edge[i].second];
        if(u==v)
            cout<<'B';
        else
        if((u==P[v][0]&&sum1[v]>0)||(v==P[u][0]&&sum2[u]>0))
            cout<<'R';
        else
        if((u==P[v][0]&&sum2[v]>0)||(v==P[u][0]&&sum1[u]>0))
            cout<<'L';
        else
            cout<<'B';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

oneway.cpp: In function 'void FindBridge(int, int)':
oneway.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gg[u].size();i++)
                 ~^~~~~~~~~~~~~
oneway.cpp: In function 'void DFSComponent(int, int)':
oneway.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gg[u].size();i++)
                 ~^~~~~~~~~~~~~
oneway.cpp: In function 'void DFSHigh(int, int)':
oneway.cpp:47:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[u].size();i++)
                 ~^~~~~~~~~~~~
oneway.cpp: In function 'void SumDFS(int, int)':
oneway.cpp:80:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[u].size();i++)
                 ~^~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:108:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<Edge.size();i++)
                 ~^~~~~~~~~~~~
oneway.cpp:137:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<Edge.size();i++)
                 ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...