Submission #152720

#	Time	Username	Problem	Language	Result	Execution time	Memory
152720		Mercenary	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	297 ms	23260 KiB

oneway

#include<bits/stdc++.h>

using namespace std;
#define taskname "A"
#define pb	push_back
#define mp 	make_pair
#ifndef LOCAL
#define cerr if(0)cout
#endif

typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
const int maxn = 1e5 + 5;

int n, m , p;

struct edge{
    int used , u , v , col;
}e[maxn];

vector<int> adj[maxn];
int num[maxn] , low[maxn];
static int nTime = 0 , nGroup = 0;

void DFS(int u){
    low[u] = num[u] = ++nTime;
    for(int c : adj[u]){
        if(e[c].used)continue;
        e[c].used = 1;
        int v = e[c].u + e[c].v - u;
        if(num[v] == 0){
            DFS(v);
            low[u] = min(low[u] , low[v]);
        }else{
            low[u] = min(low[u] , num[v]);
        }
    }
    for(int c : adj[u]){
        int v = e[c].u + e[c].v - u;
//        cout << u << " " << v << " " << c << " " << low[v] << " " << num[v] << endl;
        if(num[u] < num[v] && low[v] == num[v])e[c].col = -1;
    }
}

void DFS1(int u){
    num[u] = nGroup;
    for(int c : adj[u]){
        if(num[e[c].u + e[c].v - u] == 0 && e[c].col != -1){
            DFS1(e[c].u + e[c].v - u);
        }
    }
}

int par[maxn];
int path[maxn];

const int logn = 17;
int P[maxn][logn] , h[maxn];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> m;
    for(int i = 1 ; i <= m ; ++i){
        cin >> e[i].u >> e[i].v;
        adj[e[i].u].pb(i);
        adj[e[i].v].pb(i);
    }
    for(int i = 1 ; i <= n ; ++i){
        if(num[i] == 0)DFS(i);
    }
    fill_n(num,maxn,0);
    for(int i = 1 ; i <= n ; ++i){
        if(num[i] == 0){
            ++nGroup;
            DFS1(i);
        }
    }
    for(int i = 1 ; i <= n ; ++i){
        adj[i].clear();
    }
    for(int i = 1 ; i <= m ; ++i){
        e[i].u = num[e[i].u];
        e[i].v = num[e[i].v];
        if(e[i].col == -1){
            adj[e[i].u].pb(i);
            adj[e[i].v].pb(i);
        }
    }
    function<void(int)> DFS = [&](int u){
        low[u] = 1;
        for(int c : adj[u]){
            int v = e[c].u + e[c].v - u;
            if(low[v] == 1)continue;
            par[v] = c;
            path[v] = u;
            h[v] = h[u] + 1;
            P[v][0] = u;
            for(int i = 1 ; i < logn ; ++i){
                P[v][i] = P[P[v][i - 1]][i - 1];
            }
            DFS(v);
        }
    };
    fill_n(low,maxn,0);
    for(int i = 1 ; i <= nGroup ; ++i){
        if(low[i] == 0){
            DFS(i);
        }
    }
//    for(int i = 1 ; i <= nGroup ; ++i){
//        cout << i << " " << P[i][0] << endl;
//    }
    cin >> p;
    for(int i = 1 ; i <= p ; ++i){
        int u , v;cin >> u >> v;
        u = num[u];v = num[v];
        auto FindLCA = [&](int u , int v){
            if(h[u] < h[v])swap(u , v);
            for(int i = 0 ; i < logn ; ++i){
                if(((h[u] - h[v]) >> i) & 1){
                    u = P[u][i];
                }
            }
            if(u == v)return u;
            for(int i = logn - 1 ; i >= 0 ; --i){
                if(P[u][i] != P[v][i]){
                    u = P[u][i];
                    v = P[v][i];
                }
            }
            return P[u][0];
        };
        function<int(int)> FindPath = [&](int u){
                if(u == 0)return 0;
                if(e[par[path[u]]].col == -1)return path[u];
                return path[u] = FindPath(path[u]);
            };
        auto Travel = [&](int u , int v , int delta){
            while(h[u] > h[v]){
                int c = par[u];
//                if(e[c].col != -1)cout << c << endl;
                int pre = e[c].col;
                if(e[c].u == P[e[c].v][0]){
                    e[c].col = delta;
                }else{
                    e[c].col = 3 - delta;
                }
                u = FindPath(u);
            }
        };
        int c = FindLCA(u , v);
//        for(int j = 1 ; j <= nGroup ; ++j)cout << FindPath(j) << " ";cout << endl;
        Travel(u , c , 1);
        Travel(v , c , 2);
    }
    for(int i = 1 ; i <= m ; ++i){
        if(e[i].col <= 0)cout << "B";
        else if(e[i].col == 2)cout << "R";
        else cout << "L";
    }
}

Compilation message (stderr)

oneway.cpp: In lambda function:
oneway.cpp:148:21: warning: unused variable 'pre' [-Wunused-variable]
                 int pre = e[c].col;
                     ^~~
oneway.cpp: In function 'int main()':
oneway.cpp:65:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:66:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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