Submission #491033

#	Time	Username	Problem	Language	Result	Execution time	Memory
491033		socpite	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	0 ms	204 KiB

oneway

#include<bits/stdc++.h>
using namespace std;

#define maxn 1010
#define f first
#define s second

int n, q, timedfs = 1, ccnt = 0, m;
int sprasetable[maxn][18];
stack<int> s;
vector<vector<pair<int, int>>> graph;
vector<vector<pair<int, int>>> tree;
vector<int> edgeup;
vector<pair<int, int>> edge;
vector<int> ans;
int level[maxn];
int low[maxn];
int up[maxn];
int pos[maxn];
int num[maxn];

void build(int x){
    if(x == 18)return;
    for(int i = 1; i <= n; i++){
        if(sprasetable[i][x-1] != -1)sprasetable[i][x] = sprasetable[sprasetable[i][x-1]][x-1];
        else sprasetable[i][x] = -1;
    }
    build(x+1);
}

void DFSt(int x, int p){
    low[x]=num[x]=timedfs++;
    s.push(x);
    for(auto u: graph[x]){
        if(u.s == p)continue;
        if(!num[u.f])DFSt(u.f, u.s);
        else{
            if(num[u.f] < num[x])low[x]=min(low[x], low[u.f]);
            else low[u.f]=min(low[u.f], num[x]);
        }
    }
    if(low[x] == num[x]){
        ccnt++;
        while(!s.empty() && s.top() != x){
            pos[s.top()]=ccnt;
            s.pop();
        }
        if(!s.empty()){
            pos[s.top()]=ccnt;
            s.pop();
        }
    }
}

int travelup(int x, int distance){
    for(int i = 0; i < 18; i++){
        if(distance & (1 << i))x = sprasetable[x][i];
        if(x == -1)return -1;
    }
    return x;
}

int query(int a, int b){
    if(level[a] < level[b])swap(a, b);
    int distance = level[a]-level[b];
    a = travelup(a, distance);
    int curr=18;
    for(int i = curr; i >= 0; i--){
        if(sprasetable[a][i] != sprasetable[b][i]){
            a = sprasetable[a][i];
            b = sprasetable[b][i];
        }
    }
    if(a == b)return a;
    else return sprasetable[a][0];
}

void DFS(int x, int p){
    sprasetable[x][0]=p;
    for(auto u: tree[x]){
        if(u.f == p)continue;
        level[u.f]=level[x]+1;
        edgeup[u.f]=u.s;
        DFS(u.f, x);
    }
}

int Find(int x){
    if(up[x] < 0)return x;
    else{
        up[x]=Find(up[x]);
        return up[x];
    }
}

void Union(int a, int b){
    a = Find(a);
    b = Find(b);
    up[a]=b;
}

int main(){
    cin >> n >> m;
    graph.resize(n+1);
    edge.resize(m);
    ans.assign(m, 0);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        graph[a].push_back({b, i});
        graph[b].push_back({a, i});
        edge[i]={a, b};
    }
    /*
    DFSt(1, -1);
    graph.clear();
    edgeup.resize(n+1);
    tree.resize(ccnt+1);
    for(int i = 0; i < m; i++){
        int a = pos[edge[i].f];
        int b = pos[edge[i].s];
        if(a != b){
            tree[a].push_back({b, i});
            tree[b].push_back({a, i});
        }
    }
    for(int i = 1; i <= ccnt; i++)if(!sprasetable[i][0])DFS(i, -1);
    for(int i = 1; i <= ccnt; i++)up[i]=-1;
    build(1);
    cin >> q;
    for(int i = 0; i < q; i++){
        int a, b;
        cin >> a >> b;
        a=pos[a];
        b=pos[b];
        int anc = query(a, b);
        a = Find(a);
        while(level[anc] < level[a]){
            ans[edgeup[a]]=1;
            Union(a, sprasetable[a][0]);
            a = sprasetable[a][0];
            a = Find(a);
        }
        b = Find(b);
        while(level[anc] < level[b]){
            ans[edgeup[b]]=-1;
            Union(b, sprasetable[b][0]);
            b = sprasetable[b][0];
            b = Find(b);
        }
    }
    for(int i = 0; i < m; i++){
        if(!ans[i])cout << "B";
        else{
            int tmp = ans[i];
            if(edgeup[pos[edge[i].f]] == i)tmp*=-1;
            if(tmp == 1)cout << "L";
            else cout << "R";
        }
    }
    */
}

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