제출 #141218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
141218		12tqian	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	10 ms	8444 KiB

oneway

#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

const double PI = 4 * atan(1);

#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>

#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)

void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
void io(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    fast_io();
}
const int MAX = 1e5 + 5;
const int SZ = 1e5 + 5;
vi adj1[MAX];
vi adj[MAX];
vpi paths;
int ans[MAX];
map<pii, int> um;
map<int, int> convert;
map<pii, pii> check;
map<pii, int> ind;
map<pii, int> res;
vpi all;
vi t[MAX];
int N;
template<int SZ> struct DSU{
    int par[SZ], sz[SZ];
    DSU(){
        for(int i = 0; i<SZ; i++){
            par[i] = i;
            sz[i] = 1;
        }
    }
    int get(int x){
        if(par[x] != x){
            par[x] = get(par[x]);
        }
        return par[x];
    }
    bool unite(int x, int y){
        x = get(x);
        y = get(y);
        if(x == y){
            return false;
        }
        if(sz[x] < sz[y]){
            swap(x, y);
        }
        sz[x] += sz[y];
        par[y] = x;
        return true;
    }
};
DSU<MAX> d;
vector<vector<pair<int, int>>> fin;

void addEdge(int u, int v) {
    if(u == v) return;
    adj1[u].push_back(v), adj1[v].push_back(u);
}

int ti = 0, disc[SZ], low[SZ], comp[SZ], parent[SZ];
vector<pair<int, int>> st;

void BCCutil(int u, bool root = 0) {
    disc[u] = low[u] = ti++;
    int child = 0;
    for (int i: adj1[u]) {
        if (i != parent[u]){
            if (disc[i] == -1) {
                child ++; parent[i] = u;
                st.push_back({u,i});
                BCCutil(i);
                low[u] = min(low[u],low[i]);

                if ((root && child > 1) || (!root && disc[u] <= low[i])) { // articulation point!
                    vector<pair<int, int>> tmp;
                    while (st.back() != make_pair(u,i)) tmp.push_back(st.back()), st.pop_back();
                    tmp.push_back(st.back()), st.pop_back();
                    fin.push_back(tmp);
                }
            }
            else if (disc[i] < disc[u]) {
                low[u] = min(low[u],disc[i]);
                st.push_back({u,i});
            }
        }
    }
}

void bcc(int _N) {
    N = _N;
    for(int i = 1; i< N+1; i++){
        parent[i] = disc[i] = low[i] = -1;
    }
    for(int i = 1; i<N+1; i++){
        if (disc[i] == -1) {
            BCCutil(i,1);
            if ((st).size()) fin.push_back(st);
            st.clear();
        }
    }
}

const int LOG = 20;

int depth[MAX];
int par[MAX][LOG];


int sz;

void dfs(int cur, int prev) {
    par[cur][0] = prev;

    for (int nxt : t[cur]) {
        if (nxt == prev)
            continue;

        depth[nxt] = depth[cur] + 1;
        dfs(nxt, cur);
    }
}

int root = MAX;
vi vertices;
inline void process() {
    depth[root] = 0;
    dfs(root, root);
    for (int lvl = 0; lvl < LOG - 1; lvl ++) for (int cur: vertices) {
        int mid = par[cur][lvl];
        par[cur][lvl + 1] = par[mid][lvl];
    }
}

inline int LCA(int u, int v) {
    if (depth[u] < depth[v])
        swap(u, v);

    for (int it = LOG - 1; it >= 0; it--)
        if (depth[u] - depth[v] >= (1 << it))
            u = par[u][it];

    if (u == v)
        return u;

    for (int it = LOG - 1; it >= 0; it--) {
        if (par[u][it] != par[v][it]) {
            u = par[u][it];
            v = par[v][it];
        }
    }

    return par[u][0];
}
void markUp(int cur, int lca){
    if(cur == lca) return;
    int above = par[cur][0];
    if(check.find(mp(cur, above)) != check.end()){
        res[check[mp(cur, above)]] = 1;
    }
    else{
        res[check[mp(above, cur)]] = -1;
    }
    markUp(above, lca);
}
void markDown(int cur, int lca){
    if(cur == lca) return;
    int above = par[cur][0];
    if(check.find(mp(cur, above)) != check.end()){
        res[check[mp(cur, above)]] = -1;
    }
    else{
        res[check[mp(above, cur)]] = 1;
    }
    markDown(above, lca);
}
int main(){
    fast_io();
    int n, m;
    cin >> n >> m;
    f0r(i, m){
        int ai, bi;
        cin >> ai >> bi;
        ai--; bi--;
        ind[mp(ai, bi)] = i;
        all.eb(mp(ai, bi));
        res[mp(ai, bi)] = 0;
        adj[ai].eb(bi);
        adj[bi].eb(ai);
        addEdge(ai + 1, bi + 1);
        um[mp(ai, bi)] = 1;
        um[mp(bi, ai)] = 1;
    }
    int p;
    cin >> p;
    f0r(i, p){
        int xi, yi;
        cin >> xi >> yi;
        xi--; yi--;
        paths.eb(mp(xi, yi));
    }
    bcc(n);
    f0r(i, sz(fin)){
        if(sz(fin[i]) != 1){
            continue;
        }
        pii edge = fin[i][0];
        edge.f--;
        edge.s--;
       // cout << edge.f << " bad " << edge.s << endl;
        um[edge] = 0;
        um[mp(edge.s, edge.f)] = 0;
    }
    f0r(i, sz(fin)){
        f0r(j, sz(fin[i])){
            fin[i][j].f--;
            fin[i][j].s--;
        }
    }
    f0r(i, n){
        for(int j: adj[i]){
            if(i<j){
                //    cout << i << " " << j << " " <<  um[mp(i, j)] << endl;
                if(um[mp(i, j)] == 1){
                     //   cout << i <<" unite " << j << endl;
                    d.unite(i, j);
                }
            }
        }
    }
    set<int> use;
    f0r(i, sz(fin)){
        if(sz(fin[i]) != 1) continue;
        use.insert(d.get(fin[i][0].f));
        use.insert(d.get(fin[i][0].s));
        convert[d.get(fin[i][0].f)] = i;
    }
    int tmp = 0;
    for(auto x: use) {
        convert[x] = tmp;
        tmp++;
    }
   /* f0r(i, n){
        cout << "comp: "<< i << " " << d.get(i) << " " << convert[d.get(i)] << endl;
    }
    cout << endl;*/
    f0r(i, sz(fin)){
        if(sz(fin[i]) != 1){
            continue;
        }
   //    cout << fin[i][0].f << " " << fin[i][0].s << endl;
        int c1 = convert[d.get(fin[i][0].f)];
        int c2 = convert[d.get(fin[i][0].s)];
        if(ind.find(fin[i][0]) != ind.end()){
            check[mp(c1, c2)] = fin[i][0];
        }
        else{
            check[mp(c2, c1)] = mp(fin[i][0].s, fin[i][0].f);
        }
        root = min(root, min(c1, c2));
        t[c1].eb(c2);
        t[c2].eb(c1);
       // cout << c1 << " edge " << c2 << endl;

    }
    int sz = sz(use);
    //cout << sz << " size"<< endl;
    for(auto x: use) vertices.eb(x);
    process();
    f0r(i, p){
        if(d.get(paths[i].f) !=  d.get(paths[i].s)) {
          //  cout << i <<  " here" << endl;
            int enter = convert[d.get(paths[i].f)];
            int exit = convert[d.get(paths[i].s)];
            int lca = LCA(enter, exit);
            //cout << enter << " " << lca << " " << exit << " path" << endl;
            markUp(enter, lca);
            markDown(exit, lca);
        }
    }
    ///-1 is left 1 is right 0 is both
    string ret = "";
    f0r(i, m){
        int verify = res[all[i]];
        if(verify == 0){
            ret += "B";
        }
        else if(verify == 1){
            ret += "R";
        }
        else ret += "L";
    }
    cout << ret << endl;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

oneway.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
oneway.cpp: In function 'int main()':
oneway.cpp:306:9: warning: unused variable 'sz' [-Wunused-variable]
     int sz = sz(use);
         ^~
oneway.cpp: In function 'void io(std::__cxx11::string)':
oneway.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FIN, "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FOUT, "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~

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