Submission #1259160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259160		maxil	One-Way Streets (CEOI17_oneway)	C++20	30 / 100	3095 ms	3748 KiB

oneway

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define MASK(x) ((1LL) << (x))
#define BIT(x, i) (((x) >> (i)) & (1LL))
#define str string
#define fi first
#define se second
#define pii pair<int, int>
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endline '\n'
#define all(x) (x).begin(),(x).end()
#define log 20
#define FOR(i,l,r,val) for(int i = l;i <= r ; i = i + val)
#define FORD(i,l,r,val) for(int i = l;i >= r; i = i - val)
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return 1; }; return 0; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return 1; }; return 0; }
using namespace std;
const int N = 1e6 + 3;

int n, m, p;
vector<pii> ke, q;

bool check(int nn, int di)
{
    vector<vector<int>> g(n + 1);
    FOR(i, 0, m - 1, 1)
    {
        int u = ke[i].fi;
        int v = ke[i].se;
        if(i == nn)
        {
            if(di == 0) g[u].pb(v);
            else g[v].pb(u);
        }
        else
        {
            g[u].pb(v);
            g[v].pb(u);
        }
    }

    for(pii t : q)
    {
        int x = t.fi, y = t.se;
        vector<int> vi(n + 1, 0);
        queue<int> mp;
        vi[x] = 1;
        mp.push(x);
        bool dd = false;
        while(!mp.empty())
        {
            int u = mp.front();
            mp.pop();
            if(u == y)
            {
                dd = true;
                break;
            }
            for(int tt : g[u])
            {
                if(!vi[tt])
                {
                    vi[tt] = 1;
                    mp.push(tt);
                }
            }
        }
        if(!dd) return false;
    }
    return true;
}
int main()
{
    faster
   // freopen("way.inp","r",stdin);
    //freopen("way.out","w",stdout);

    cin >> n >> m;
    ke.resize(m);
    FOR(i, 0, m - 1, 1) cin >> ke[i].fi >> ke[i].se;

    cin >> p;
    q.resize(p);
    FOR(i, 0, p - 1, 1) cin >> q[i].fi >> q[i].se;

    str ans = "";
    FOR(i, 0, m - 1, 1)
    {
        bool R = check(i, 0);
        bool L = check(i, 1);
        if (R && L) ans += 'B';
        else if (R) ans += 'R';
        else ans += 'L';
    }

    cout << ans;
}

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