제출 #584190

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584190		nohaxjustsoflo	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	3 ms	5076 KiB

oneway

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
//mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN = 1e5+5;
const int mod = 998244353;
const int mxlogN = 20;
const int mxK = 26;
const ll inf = 1e9;

struct edge
{
    int u, v, root; bool cut; int way;
    int other(int i)
    {
        return i^u^v;
    }
};
edge es[mxN];
int vis[mxN],lowlink[mxN],_time[mxN],_timer;
vector<int> adj[mxN];
void dfs(int i, int p=-1) ///parent edge
{
    lowlink[i]=_time[i]=_timer++;
    vis[i]=1;
    for(int e:adj[i])
    {
        int j=es[e].other(i);
        if(e==p||vis[j]==2) continue;
        if(vis[j]) lowlink[i]=min(lowlink[i],_time[j]);
        else
        {
            dfs(j,e);
            lowlink[i]=min(lowlink[i],lowlink[j]);
            if(lowlink[j]>_time[i]) es[e].cut=1;
        }
    }
    vis[i]=2;
}
int sz=0;
int root[mxN];
void dfs2(int i, int r)
{
    vis[i]=1;
    root[i]=r;
    for(int e:adj[i])
    {
        int j=es[e].other(i);
        if(es[e].cut||vis[j]) continue;
        dfs2(j,r);
    }
}
vector<int> adjc[mxN];
int up[mxlogN][mxN], down[mxN], where[mxN], pe[mxN];
void dfs3(int i, int p=-1, int d=0)
{
    if(~p) up[0][i]=es[p].other(i);
    else up[0][i]=i;
    pe[i]=p;
    vis[i]=1;
    down[i]=d;
    where[i]=i;
    for(int j=1; j<mxlogN; j++) up[j][i]=up[j-1][up[j-1][i]];
    for(int e:adjc[i]) if(e!=p) dfs3(es[e].other(i),e,d+1);
}
int goup(int i, int k)
{
    if(!k) return i;
    for(int j=mxlogN-1; j>=0; j--)
    {
        if(k>(1<<j))
        {
            k-=1<<j;
            i=up[j][i];
        }
    }
    return up[0][i];
}
int find_lca(int i, int j)
{
    if(down[i]<down[j]) swap(i,j);
    i = goup(i,down[i]-down[j]);
    if(i==j) return i;
    for(int k=mxlogN-1; k>=0; k--)
    {
        if(up[k][i]!=up[k][j])
        {
            i=up[k][i], j=up[k][j];
        }
    }
    return up[0][i];
}
void setup(int n, int m)
{
    dfs(0);
    for(int i=0; i<n; i++) vis[i]=0;
    for(int i=0; i<n; i++) if(!vis[i]) dfs2(i,sz++);
    for(int i=0; i<m; i++)
    {
        if(es[i].cut)
        {
            int u=root[es[i].u], v=root[es[i].v];
            es[i].u=u, es[i].v=v;
            adjc[u].push_back(i);
            adjc[v].push_back(i);
        }
    }
    for(int i=0; i<sz; i++) vis[i]=0;
    for(int i=0; i<sz; i++) if(!vis[i]) dfs3(i);
}
void clear_all()
{
    ///clear
}
int get(int i)
{
    if(!where[i]) return where[i];
    if(~es[pe[where[i]]].way) where[i]=get(up[0][where[i]]);
    return where[i];
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    for(int i=0; i<m; i++)
    {
        int u,v; cin >> u >> v; u--, v--;
        es[i]={u,v};
        es[i].cut=0;
        es[i].root=-1;
        es[i].way=-1;
        adj[u].push_back(i);
        adj[v].push_back(i);
    }
    setup(n,m);
    int p; cin >> p;
    while(p--)
    {
        int x, y; cin >> x >> y; x--, y--;
        x=root[x], y=root[y];
        int lca=find_lca(x,y);
        /*while(1)
        {
            ///set p link
            x=get(x);
            if(down[x]<=down[lca]) break;
            if(es[pe[x]].u==x) es[pe[x]].way=0;
            else es[pe[x]].way=1;
        }
        while(1)
        {
            y=get(y);
            if(down[y]<=down[lca]) break;
            if(es[pe[y]].v==y) es[pe[y]].way=0;
            else es[pe[y]].way=1;
        }*/
    }
    for(int i=0; i<m; i++)
    {
        if(!~es[i].way) cout << "B";
        else if(es[i].way) cout << "L";
        else cout << "R";
    }
    cout << "\n";
}
/*
2
7 7
1 5
3 5
3 7
1 7
6 7
4 7
4 6
7 7
1 5
3 5
3 7
1 7
6 7
4 7
4 6
*/

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

oneway.cpp: In function 'int main()':
oneway.cpp:152:13: warning: unused variable 'lca' [-Wunused-variable]
  152 |         int lca=find_lca(x,y);
      |             ^~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40