Submission #1011362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011362		NValchanov	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	184 ms	104332 KiB

oneway

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40