Submission #1259054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259054		sitingfake	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	3 ms	4928 KiB

oneway

#include<bits/stdc++.h>
using namespace std;

// define

#define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define ll long long
#define ld double
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) (((x)>>(i))&1LL)
#define flip(x,i) ((x)^(1LL<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define sitingfake 1
#define orz 1
#define exist __exist
#define ends __ends
#define visit visited
#define left __left
#define right __right

//constant

const ll mod = 1e9 + 7;
const long long linf = 4557430888798830399;
const int inf = 1061109567;
const int maxarr = 1e6 + 5;
int dx[] = {0 , -1 , 0 , 1};
int dy[] = {-1 , 0 , 1 , 0};

template<typename T> bool maximize(T &a, const T &b)
{
    if(a < b) {a = b; return 1;}
    return 0;
}

template<typename T> bool minimize(T &a, const T &b)
{
    if(a > b) {a = b; return 1;}
    return 0;
}

inline void Plus(ll & a ,ll b)
{
    b %= mod;
    a += b;
    if(a >= mod) a -= mod;
    if(a < 0) a += mod;
    return;
}

inline void Mul(ll & a, ll b)
{
    a %= mod; b %= mod;
    a *= b;
    a %= mod;
    return;
}

//code

const int maxn = 1e5 + 7;

ii edges[maxn];

char ans[maxn];

vector <iii> g[maxn];

vector <ii> a[maxn];
vector <int> roots;

int low[maxn] , id[maxn] , scc[maxn] , components , timer;

int in[maxn] , out[maxn];


stack <int> st;

int depth[maxn] , par[maxn][20];

int dp[maxn];

int n , m , q;

void dfs(int u , int p)
{
    low[u] = id[u] = ++timer;
    st.push(u);

    for(ii i : a[u])
    {
        int v = i.fi;
        int np = i.se;
        if(np == p) continue;

        if(!id[v])
        {
            dfs(v , np);
            low[u] = min(low[u] , low[v]);
        }
        else low[u] = min(low[u] , id[v]);
    }

    if(low[u] == id[u])
    {
        ++components;
        int v;

        do
        {
            v = st.top();
            st.pop();
            scc[v] = components;
        }while(v != u);
    }
}


void DFS(int u , int p)
{
    in[u] = ++timer;
    for(iii it : g[u])
    {
        int v = it.se.fi;
        if(v != p)
        {
            DFS(v , u);
        }
    }
    out[u] = timer;
}

bool inside(int u , int v)
{
    return in[u] <= in[v] && out[v] <= out[u];
}


void Push(int u , int p)
{
    for(iii i : g[u])
    {
        int t = i.fi;
        int id = i.se.se;
        int v = i.se.fi;

        if(v != p)
        {
            Push(v , u);
            dp[u] += dp[v];

            if(dp[v] == 1)
            {
                if(!t) ans[id] = 'L';
                else ans[id] = 'R';
            }
            else if(dp[v] == -1)
            {
                if(!t) ans[id] = 'R';
                else ans[id] = 'L';
            }
            else ans[id] = 'B';
        }
    }
}


void solve(void)
{
    cin >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int u , v;
        cin >> u >> v;
        edges[i] = ii(u , v);
        a[u].push_back(ii(v , i));
        a[v].push_back(ii(u , i));
    }

    for(int i = 1; i <= n; i++)
    {
        if(!id[i])
        {
            dfs(i , -1);
        }
    }

    for(int i = 1; i <= m; i++)
    {
        int u = edges[i].fi;
        int v = edges[i].se;
        if(scc[u] == scc[v])
        {
            ans[i] = 'B';
        }
        else
        {
            u = scc[u];
            v = scc[v];
            g[u].push_back(iii(0 , ii(v , i)));
            g[v].push_back(iii(1 , ii(u , i)));
        }
    }

    timer = 0;

    for(int i = 1; i <= components; i++)
    {
        if(!in[i])
        {
            roots.push_back(i);
            DFS(i , -1);
        }
    }

    cin >> q;

    while(q--)
    {
        int u , v;
        cin >> u >> v;
        if(scc[u] != scc[v])
        {
            u = scc[u] , v = scc[v];

            if(inside(u , v))
            {
                dp[v]--;
                dp[u]++;
            }
            else
            {
                dp[u]++;
                dp[v]--;
            }
        }
    }

    for(int i : roots)
    {
        Push(i , -1);
    }

    for(int i = 1; i <= m; i++) cout << ans[i];
}
/**
**/
signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   #define task ""

   if(fopen(task".inp","r"))
   {
       freopen(task".inp","r",stdin);
       freopen(task".out","w",stdout);
   }

   int tc; tc = 1;

   while(tc--) solve();

   //execute;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:263:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  263 |        freopen(task".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:264:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  264 |        freopen(task".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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