oj.uz

Submission #1033178

# Submission time Handle Problem Language Result Execution time Memory
1033178 2024-07-24T13:45:26 Z MarwenElarbi One-Way Streets (CEOI17_oneway) C++17
100 / 100
 91 ms 35664 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int nax=1e5+5;
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
vector<pair<int,int>> edge(nax);
vector<pair<int,int>> adj[nax];
string ans;
int depth[nax];
int parent[nax];
vector<pair<int,int>> tre[nax];
vector<int> low[nax];
vector<int> up[nax];
bool vis[nax];
int dp[nax];
void dfs(int x,int p){
    vis[x]=true;
    for(auto u:adj[x]){
        if (u.se==p) continue;
        if (vis[u.fi]){
            if (depth[u.fi]>depth[x]) continue;
            low[u.fi].pb(x);
            up[x].pb(u.fi);
            continue;
        }
        depth[u.fi]=depth[x]+1;
        tre[x].pb(u);
        tre[u.fi].pb({x,u.se});
        dfs(u.fi,u.se);
    }
    return;
}
void trav(int x,int p){
    dp[x]=up[x].size()-low[x].size();
    for(auto u:tre[x]){
        if (u.fi==p) continue;
        trav(u.fi,x);
        dp[x]+=dp[u.fi];
    }
    //cout <<x<<" "<<up[x].size()<<" "<<low[x].size()<<" "<<dp[x]<<endl;
    if (dp[x]==0){
        parent[x]=x;
    }else parent[x]=p;
}
int find(int x){
    if(x==parent[x]) return x;
    return parent[x]=find(parent[x]);
}
int bj[nax][20];
void compute(int x,int p){
    for (int i = 1; i < 20; ++i)
    {
        bj[x][i]=bj[bj[x][i-1]][i-1];
    }
    for(auto u:tre[x]){
        if(u.fi==p) continue;
        bj[u.fi][0]=x;
        compute(u.fi,x);
    }
    return;
}
int jump(int x,int d){
    for (int i = 19; i >= 0; --i)
    {
        if(d&(1<<i)) x=bj[x][i];
    }
    return x;
}
int lca(int x,int y){
    if(depth[x]<depth[y]) swap(x,y);
    x=jump(x,depth[x]-depth[y]);
    if(x==y) return x;
    for (int i = 19; i >= 0 ;--i)
    {
        if(bj[x][i]!=bj[y][i]){
            x=bj[x][i];
            y=bj[y][i];
        }
    }
    return bj[x][0]; 
}
int main()
{
    optimise;
    int n,m;
    cin>>n>>m;
    for (int i = 0; i < m; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        edge[i]={x,y};
        adj[x].pb({y,i});
        adj[y].pb({x,i});
        ans.pb('B');
    }
    for (int i = 0; i < n; ++i)
    {
        if(vis[i]) continue;
        parent[i]=i;
        dfs(i,-1);
        trav(i,-1);
        compute(i,-1);
    }
    int q;
    cin>>q;
    for (int i = 0; i < q; i++)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        x=find(x);
        y=find(y);
        int z=lca(find(x),find(y));
        z=find(z);
        while(find(x)!=find(z)){
            x=find(x);
            if(x==find(z)) break;
            for(auto u:tre[x]){
                if(u.fi==bj[x][0]){
                    ans[u.se]=(edge[u.se].fi==u.fi ? 'L' : 'R');
                    parent[x]=u.fi;
                    break;
                }
            }
        }
        while(find(y)!=find(z)){
            y=find(y);
            if(y==find(z)) break;
            for(auto u:tre[y]){
                if(u.fi==bj[y][0]){
                    ans[u.se]=(edge[u.se].fi==u.fi ? 'R' : 'L');
                    parent[y]=u.fi;
                }
            }
        }
    }
    cout <<ans<<endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10584 KB Output is correct
2 Correct 6 ms 10584 KB Output is correct
3 Correct 5 ms 10588 KB Output is correct
4 Correct 5 ms 10824 KB Output is correct
5 Correct 6 ms 10840 KB Output is correct
6 Correct 5 ms 10844 KB Output is correct
7 Correct 5 ms 10844 KB Output is correct
8 Correct 5 ms 10844 KB Output is correct
9 Correct 6 ms 10588 KB Output is correct
10 Correct 5 ms 10588 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10584 KB Output is correct
2 Correct 6 ms 10584 KB Output is correct
3 Correct 5 ms 10588 KB Output is correct
4 Correct 5 ms 10824 KB Output is correct
5 Correct 6 ms 10840 KB Output is correct
6 Correct 5 ms 10844 KB Output is correct
7 Correct 5 ms 10844 KB Output is correct
8 Correct 5 ms 10844 KB Output is correct
9 Correct 6 ms 10588 KB Output is correct
10 Correct 5 ms 10588 KB Output is correct
11 Correct 47 ms 19660 KB Output is correct
12 Correct 48 ms 22212 KB Output is correct
13 Correct 56 ms 25944 KB Output is correct
14 Correct 71 ms 29520 KB Output is correct
15 Correct 70 ms 30380 KB Output is correct
16 Correct 64 ms 28500 KB Output is correct
17 Correct 67 ms 30544 KB Output is correct
18 Correct 60 ms 28352 KB Output is correct
19 Correct 68 ms 32084 KB Output is correct
20 Correct 50 ms 24404 KB Output is correct
21 Correct 48 ms 24148 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10584 KB Output is correct
2 Correct 6 ms 10584 KB Output is correct
3 Correct 5 ms 10588 KB Output is correct
4 Correct 5 ms 10824 KB Output is correct
5 Correct 6 ms 10840 KB Output is correct
6 Correct 5 ms 10844 KB Output is correct
7 Correct 5 ms 10844 KB Output is correct
8 Correct 5 ms 10844 KB Output is correct
9 Correct 6 ms 10588 KB Output is correct
10 Correct 5 ms 10588 KB Output is correct
11 Correct 47 ms 19660 KB Output is correct
12 Correct 48 ms 22212 KB Output is correct
13 Correct 56 ms 25944 KB Output is correct
14 Correct 71 ms 29520 KB Output is correct
15 Correct 70 ms 30380 KB Output is correct
16 Correct 64 ms 28500 KB Output is correct
17 Correct 67 ms 30544 KB Output is correct
18 Correct 60 ms 28352 KB Output is correct
19 Correct 68 ms 32084 KB Output is correct
20 Correct 50 ms 24404 KB Output is correct
21 Correct 48 ms 24148 KB Output is correct
22 Correct 91 ms 31572 KB Output is correct
23 Correct 88 ms 29520 KB Output is correct
24 Correct 87 ms 29724 KB Output is correct
25 Correct 90 ms 35664 KB Output is correct
26 Correct 85 ms 31060 KB Output is correct
27 Correct 84 ms 29520 KB Output is correct
28 Correct 27 ms 14928 KB Output is correct
29 Correct 62 ms 25160 KB Output is correct
30 Correct 60 ms 25280 KB Output is correct
31 Correct 68 ms 25684 KB Output is correct
32 Correct 68 ms 29776 KB Output is correct