제출 #1193475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193475		sitingfake	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	3 ms	5184 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

//constant

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

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)
{
    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;

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

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

bool visited[maxn];

ii edges[maxn];
vector <ii> a[maxn];
vector <iii> G[maxn]; // 0 = right , 1 = left;

stack <int> s;

char ans[maxn];

int n , m , k;

ii p[maxn];

void dfs(int u , int p)
{
    low[u] = id[u] = ++ timer;
    s.push(u);
    for(ii i : a[u])
    {
        int v = i.fi;
        int np = i.se;
        if(p == np) 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])
    {
        int v;
        ++tplt;
        do
        {
            v = s.top();
            s.pop();
            scc[v] = tplt;
        } while(u != v);
    }
}

void DFS(int u , int p)
{
    visited[u] = 1;
    for(iii i : G[u])
    {
        int v = i.se.fi;
        if(v == p) continue;

        depth[v] = depth[u] + 1;
        par[v][0] = u;

        DFS(v , u);
    }
}

void Prepare()
{
    for(int j = 1; (1 << j) <= tplt ;j ++)
    {
        for(int i = 1; i <= tplt ;i++)
        {
            par[i][j] = par[par[i][j-1]][j-1];
        }
    }
}

int lca(int u ,int v)
{
    if(depth[u] < depth[v]) swap(u , v);

    int diff = depth[u] - depth[v];

    for(int i = 0 ; (1 << i) <= diff ; i++)
    {
        if(bit(diff , i))
        {
            u = par[u][i];
        }
    }

    if(u == v) return u;

    for(int i = 19; i >= 0 ; i--)
    {
        if(par[u][i] != par[v][i])
        {
            v = par[v][i];
            u = par[u][i];
        }
    }

    return par[u][0];
}

void Query(int u , int v)
{
    int lc = lca(u , v);
    dp[u] ^= 1;
    dp[lc] ^= 1;
    f[u] ++;
    f[v] ++;

    f[lc] -= 2;
}

void get(int u ,int p)
{
    visited[u] = 1;
    for(iii i : G[u])
    {
        int v = i.se.fi;
        int id = i.se.se;

        int val = i.fi;

        if(v != p)
        {
            get(v , u);
            if(f[v] > 0)
            {
                val ^= dp[v];

                if(val == 0) ans[id] = 'R';
                else ans[id] = 'L';
            }
            else ans[id] = 'B';

            dp[u] ^= dp[v];
            f[u] += f[v];
        }
    }
}

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

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

        edges[i] = ii(u , v);
    }

    cin >> k;

    for(int i = 1; i <= k ;i++) cin >> p[i].fi >> p[i].se;


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

    for(int i = 1; i <= m ;i++)
    {
        int u = scc[edges[i].fi] , v = scc[edges[i].se];

        if(u == v)
        {
            ans[i] = 'B';
        }
        else
        {
            G[u].push_back(iii(0 , ii(v , i)));
            G[v].push_back(iii(1 , ii(u , i)));
        }
    }

    for(int i = 1; i <= tplt ; i++)
    {
        if(!visited[i])
        {
            DFS(i , -1);
        }
    }

    Prepare();

    for(int i = 1; i <= k ;i++)
    {
        if(scc[p[i].fi] != scc[p[i].se])
        {
            Query(scc[p[i].fi] , scc[p[i].se]);
        }
    }

    ms(visited , 0);

    for(int i = 1; i <= tplt ;i++)
    {
        if(!visited[i]) get(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;
}

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

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

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