제출 #197447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
197447		quocnguyen1012	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	363 ms	34860 KiB

oneway

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define Task "ONEWAY"

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;

int nTime=0;
vector <int> adj[maxn]; 
int Visited[maxn], Low[maxn], Parent[maxn]; 
int U[maxn], V[maxn];
int N, M, P;
int st[maxn], en[maxn];
bool Bridge[maxn];

bool minimize(int &a, int b){ 
	if (a>b) a=b; 
	else return false; 
	return true; 
}

void visit(int u){
	///cerr << u << ' ' << Parent[u] << '\n';
    Low[u] = Visited[u] = ++nTime;
    for (auto it : adj[u]){
		int v = U[it] + V[it] - u;
		if (it!=Parent[u]){
			if (Visited[v]) 
				minimize(Low[u], Visited[v]);
			else {
				Parent[v]=it;
				visit(v); 
				minimize(Low[u], Low[v]);
				if (Low[v]>=Visited[v]) 
					Bridge[it] = 1;
			}
		}
	}
}

bool vis[maxn];
int comp[maxn];
int SCC = 0;

void dfs (int u){
	vis[u] = 1;
	comp[u] = SCC;
	for (auto it : adj[u]){
		if (Bridge[it]) continue;
		int v = U[it] + V[it] - u;
		if (!vis[v]) dfs (v);
	}
}

vector <pair <int, int>> G[maxn];
int p[maxn][21];
int cnt[maxn];
int lca(int x,int y){
    if (cnt[x]<cnt[y])
         swap (x,y);
    for(int k=20;k>=0;--k)
    {
        if (cnt[p[x][k]]>=cnt[y])
        {
            x=p[x][k];
        }
    }
    if (x==y)
        return x;
    for (int k=20;k>=0;--k)
    {
        if (p[x][k]!=p[y][k])
        {
            x=p[x][k];
            y=p[y][k];
        }
    }
    return p[x][0];
    //cerr<<
}

pair <int, int> par[maxn];

void findcnt (int u, int P){
	for (auto it : G[u]){
		if (it.fi != P){
			cnt[it.fi] = cnt[u] + 1;
			p[it.fi][0] = u;
			par[it.fi] = mp (u, it.se);
			findcnt (it.fi, u);
		}
	}
}

void Init_LCA (void){
	for (int i=1; i<=SCC; ++i){
		if (cnt[i] == 0) cnt[i] = 1, findcnt (i, 0);
	}
	for (int k=1; (1<<k)<=SCC; k++)
		for (int i=1; i<=SCC; ++i)
			p[i][k] = p[p[i][k-1]][k-1];
}

char res[maxn];

void query (int u, int v, int direct){
	int p = par[u].fi, id = par[u].se;
	if (u == v) return;
	if (res[id] != '?') return;
	if (direct == 1){
		if (comp[U[id]] == u) res[id] = 'R';
		else res[id] = 'L';
	}
	else {
		if (comp[U[id]] == u) res[id] = 'L';
		else res[id] = 'R';
	}
	query (p, v, direct);
}

struct Query{
	int st, en, direct;
	bool operator < (const Query & other) const {
		return st < other.st;
	}
};

signed main (void){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if (fopen (Task".INP", "r")){
		freopen (Task".INP", "r", stdin);
		freopen (Task".OUT", "w", stdout);
	}
	cin >> N >> M;
	for (int i=1; i<=M; ++i){
		cin >> U[i] >> V[i];
		adj[U[i]].pb (i); adj[V[i]].pb (i);
	}
	cin >> P;
	for (int i=1; i<=P; ++i)
		cin >> st[i] >> en[i];
	for (int i=1; i<=N; ++i){
		if (Visited[i] == 0){
			visit(i);
		}
	}
	for (int i=1; i<=N; ++i){
		if (vis[i] == 0){
			++SCC;
			dfs (i);
		}
	}
	for (int i=1; i<=M; ++i){
		if (Bridge[i]){
			G[comp[U[i]]].pb (mp (comp[V[i]], i));
			G[comp[V[i]]].pb (mp (comp[U[i]], i));
		}
	}
	Init_LCA();
	fill (begin(res), end(res), '?');
	///for (int i=1; i<=N; ++i) cerr << comp[i] << '\n';
	vector <pair <int, Query>> go;
	for (int i=1; i<=P; ++i){
		st[i] = comp[st[i]], en[i] = comp[en[i]];
		int lc = lca (st[i], en[i]);
		///query (st[i], lc, 1);
		///query (en[i], lc, -1);
		Query rnd = {st[i], lc, 1};
		go.pb (mp (cnt[lc], rnd));
		rnd.st = en[i], rnd.direct = -1;
		go.pb (mp (cnt[lc], rnd));
	}
	sort (go.begin(), go.end());
	for (auto all : go){
		query (all.se.st, all.se.en, all.se.direct);
	}
	for (int i=1; i<=M; ++i){
		if (res[i] == '?') cout << 'B';
		else cout << res[i];
	}
}

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

oneway.cpp: In function 'int main()':
oneway.cpp:137:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen (Task".INP", "r", stdin);
   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:138:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen (Task".OUT", "w", stdout);
   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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