oj.uz

Submission #1011362

# Submission time Handle Problem Language Result Execution time Memory
1011362 2024-06-30T12:26:16 Z NValchanov One-Way Streets (CEOI17_oneway) C++17
100 / 100
 184 ms 104332 KB 
#include<bits/stdc++.h>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
const ll MAXN = 1e6 + 10;
const ll MAXM = 1e6 + 10;
const ll MAXP = 1e6 + 10;
const ll MAXLOG = 30;
 
struct edge
{
    ll u,v,idx;
    edge(){};
    edge(ll _u, ll _v, ll _idx)
    {
        u = _u;
        v = _v;
        idx = _idx;
    }
};
 
struct path
{
    ll u,v,l;
    path(){};
    path(ll _u, ll _v, ll _l)
    {
        u = _u;
        v = _v;
        l = _l;
    }
};
 
ll n,m,p;
edge edges[MAXM];
vector < edge > adj[MAXN];
vector < edge > badj[MAXN];
vector < pair < ll, ll > > order_paths;
path paths[MAXP];
bool is_bridge[MAXM];
ll bcomp[MAXN];
char ans[MAXN];
ll lift[MAXN][MAXLOG];
bool visited[MAXN];
ll direction[MAXN];
ll depth[MAXN];
edge parent[MAXN];
ll low[MAXN];
ll tin[MAXN];
ll tim;
ll comp_cnt;
 
void find_bridges(ll u, ll par_edge)
{
    tin[u] = low[u] = ++tim;
 
    for(edge nb : adj[u])
    {
        ll v = nb.v;
        ll idx = nb.idx;
 
        if(idx == par_edge)
            continue;
 
        if(tin[v])
        {
            low[u] = min(low[u], tin[v]);
        }
        else
        {
            find_bridges(v, idx);
            low[u] = min(low[u], low[v]);
 
            if(tin[u] < low[v])
                is_bridge[idx] = true;
        }
    }
}
 
void find_components(ll u, ll comp)
{
    visited[u] = true;
    bcomp[u] = comp;
 
    for(edge nb : adj[u])
    {
        ll v = nb.v;
        ll idx = nb.idx;
 
        if(!visited[v] && !is_bridge[idx])
            find_components(v, comp);
    }
}
 
void dfs(ll u, ll par, ll par_edge)
{
 
   /// cout << u << " " << par << " " << par_edge << endl;
 
    depth[u] = depth[par] + 1;
    parent[u].v = par;
    parent[u].idx = par_edge;
    lift[u][0] = par;
 
    for(edge nb : badj[u])
    {
        ll v = nb.v;
        ll idx = nb.idx;
 
        if(v != par)
            dfs(v, u, idx);
    }
}
 
void fill_lift()
{
    for(int j = 1; j < MAXLOG; j++)
    {
        for(int i = 1; i <= comp_cnt; i++)
        {
            lift[i][j] = lift[lift[i][j - 1]][j - 1];
        }
    }
    /**
    for(int j = 0; j < MAXLOG; j++)
    {
        for(int i = 1; i <= comp_cnt; i++)
        {
            cout << lift[i][j] << " ";
        }
        cout << endl;
    }
    */
}
 
ll find_lca(ll u, ll v)
{
    if(depth[u] < depth[v])
        swap(u, v);
 
    ll diff = depth[u] - depth[v];
 
    for(int j = MAXLOG - 1; j >= 0; j--)
    {
        if(diff >= (1LL << j))
        {
            diff -= (1LL << j);
            u = lift[u][j];
        }
    }
 
    if(u == v)
        return u;
 
    for(int j = MAXLOG - 1; j >= 0; j--)
    {
        if(lift[u][j] != lift[v][j])
        {
            u = lift[u][j];
            v = lift[v][j];
        }
    }
 
    return lift[u][0];
}
 
void direct_edges(ll from, ll to, ll type)
{
    if(from == to)
        return;
 
    if(direction[from] == 0)
    {
        direction[from] = type;
 
        ll u = parent[from].v;
        ll idx = parent[from].idx;
 
        edge e = edges[idx];
 
        ll bu = bcomp[e.u];
        ll bv = bcomp[e.v];
 
        if(type == 1)
        {
            if(bu == from && bv == u)
                ans[idx] = 'R';
            else
                ans[idx] = 'L';
        }
        else if(type == 2)
        {
            if(bu == u && bv == from)
                ans[idx] = 'R';
            else
                ans[idx] = 'L';
        }
        else
        {
            assert(false);
        }
        direct_edges(u, to, type);
    }
    else
    {
        if(direction[from] != type)
        {
            cout << "IMPOSSIBLE" << endl;
            assert(false);
        }
    }
}
 
void read()
{
    cin >> n >> m;
 
    for(int i = 1; i <= m; i++)
    {
        ll u,v;
        cin >> u >> v;
        edge e = edge(u,v,i);
 
        edges[i] = e;
 
        adj[u].push_back(e);
        swap(e.u, e.v);
        adj[v].push_back(e);
    }
}
 
void make_bridge_graph()
{
    for(int i = 1; i <= n; i++)
    {
        if(!tin[i])
            find_bridges(i, 0);
    }
 
    for(int i = 1; i <= n; i++)
    {
        if(!visited[i])
            find_components(i, ++comp_cnt);
    }
 
    /**
    for(int i = 1; i <= n; i++)
    {
        cout << "Vertex " << i << " is in bridge component " << bcomp[i] << endl;
    }
    */
 
    for(edge e : edges)
    {
        ll u = e.u;
        ll v = e.v;
        ll idx = e.idx;
 
        if(!is_bridge[e.idx])
            continue;
 
        ll bu = bcomp[u];
        ll bv = bcomp[v];
 
        badj[bu].push_back(edge(bu, bv, idx));
        badj[bv].push_back(edge(bv, bu, idx));
    }
 
    /**
    for(int i = 1; i <= comp_cnt; i++)
    {
        cout << "Neighbours of " << i << " are : " << endl;
        for(edge nb : badj[i])
        {
            cout << "  - " << nb.v << endl;
        }
    }
    */
}
 
void make_lift()
{
    for(int i = 1; i <= comp_cnt; i++)
    {
        if(!depth[i])
        {
            dfs(i, 0, 0);
        }
    }
    /*
    for(int i = 1; i <= comp_cnt; i++)
    {
        cout << "Depth of bridge component " << i << " is " << depth[i] << endl;
    }
    */
    fill_lift();
}
 
void init_ans()
{
    for(int i = 1; i <= m; i++)
    {
        ans[i] = 'B';
    }
}
 
void process_paths()
{
    cin >> p;
    for(int i = 1; i <= p; i++)
    {
        ll u,v;
        cin >> u >> v;
        u = bcomp[u];
        v = bcomp[v];
        ll l = find_lca(u,v);
        paths[i] = path(u, v, l);
 
        order_paths.push_back(make_pair(depth[l], i));
    }
}
 
void solve()
{
    sort(order_paths.begin(), order_paths.end());
 
    for(pair < ll, ll > cur_path : order_paths)
    {
        ll idx = cur_path.second;
        ll u = paths[idx].u;
        ll v = paths[idx].v;
        ll l = paths[idx].l;
 
        direct_edges(u, l, 1);
        direct_edges(v, l, 2);
    }
}
 
void print()
{
    for(int i = 1; i <= m; i++)
    {
        cout << ans[i];
    }
    cout << endl;
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
 
	read();
	make_bridge_graph();
	make_lift();
	init_ans();
	process_paths();
	solve();
	print();
 
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47452 KB Output is correct
2 Correct 20 ms 47452 KB Output is correct
3 Correct 20 ms 47708 KB Output is correct
4 Correct 29 ms 47964 KB Output is correct
5 Correct 21 ms 47968 KB Output is correct
6 Correct 21 ms 47452 KB Output is correct
7 Correct 25 ms 47972 KB Output is correct
8 Correct 21 ms 47964 KB Output is correct
9 Correct 21 ms 47452 KB Output is correct
10 Correct 21 ms 47708 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47452 KB Output is correct
2 Correct 20 ms 47452 KB Output is correct
3 Correct 20 ms 47708 KB Output is correct
4 Correct 29 ms 47964 KB Output is correct
5 Correct 21 ms 47968 KB Output is correct
6 Correct 21 ms 47452 KB Output is correct
7 Correct 25 ms 47972 KB Output is correct
8 Correct 21 ms 47964 KB Output is correct
9 Correct 21 ms 47452 KB Output is correct
10 Correct 21 ms 47708 KB Output is correct
11 Correct 54 ms 60168 KB Output is correct
12 Correct 56 ms 61272 KB Output is correct
13 Correct 66 ms 63848 KB Output is correct
14 Correct 73 ms 71076 KB Output is correct
15 Correct 74 ms 74664 KB Output is correct
16 Correct 104 ms 93400 KB Output is correct
17 Correct 102 ms 95932 KB Output is correct
18 Correct 100 ms 94140 KB Output is correct
19 Correct 94 ms 96972 KB Output is correct
20 Correct 61 ms 60244 KB Output is correct
21 Correct 51 ms 60484 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47452 KB Output is correct
2 Correct 20 ms 47452 KB Output is correct
3 Correct 20 ms 47708 KB Output is correct
4 Correct 29 ms 47964 KB Output is correct
5 Correct 21 ms 47968 KB Output is correct
6 Correct 21 ms 47452 KB Output is correct
7 Correct 25 ms 47972 KB Output is correct
8 Correct 21 ms 47964 KB Output is correct
9 Correct 21 ms 47452 KB Output is correct
10 Correct 21 ms 47708 KB Output is correct
11 Correct 54 ms 60168 KB Output is correct
12 Correct 56 ms 61272 KB Output is correct
13 Correct 66 ms 63848 KB Output is correct
14 Correct 73 ms 71076 KB Output is correct
15 Correct 74 ms 74664 KB Output is correct
16 Correct 104 ms 93400 KB Output is correct
17 Correct 102 ms 95932 KB Output is correct
18 Correct 100 ms 94140 KB Output is correct
19 Correct 94 ms 96972 KB Output is correct
20 Correct 61 ms 60244 KB Output is correct
21 Correct 51 ms 60484 KB Output is correct
22 Correct 184 ms 101120 KB Output is correct
23 Correct 171 ms 99424 KB Output is correct
24 Correct 166 ms 99264 KB Output is correct
25 Correct 177 ms 104332 KB Output is correct
26 Correct 173 ms 100672 KB Output is correct
27 Correct 174 ms 99520 KB Output is correct
28 Correct 49 ms 61276 KB Output is correct
29 Correct 77 ms 65212 KB Output is correct
30 Correct 87 ms 65328 KB Output is correct
31 Correct 76 ms 65476 KB Output is correct
32 Correct 108 ms 77360 KB Output is correct