제출 #1024819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1024819		JuliaTatad	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	2 ms	860 KiB

oneway

#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <algorithm>

using namespace std;

int n, m, p; 
int INF = 2 * 1e9;
vector<vector<int>> gr;
vector<bool> used;
vector<int> comp; vector<vector<int>> cgr;
vector<int> d, dp;
vector<char> sol;
set<pair<int, int>> done;
vector<vector<int>> mp;
vector<int> bridges; 
vector<int> ts, depth, changesx, changesy; vector<bool> vis;
vector<vector<int>> bj;


map<pair<int, int>, pair<char, int>> translate;
vector<int> parents;

struct Edge {
	int from, to, num; bool is_bridge;
	Edge() {}
	Edge(int from, int to, int num) : from(from), to(to), num(num), is_bridge(false) {}
};

vector<Edge> edges;

void dfs(int v, int pnum = -1, int p = -1) {
	used[v] = true;
	if (p == -1) {
		d[v] = 0;
	}
	else {
		d[v] = d[p] + 1;
	}
	dp[v] = INF;
	for (auto e : gr[v]) {
		Edge cur = edges[e];
		if (!used[cur.to]) {
			dfs(cur.to, cur.num, v); dp[v] = min(dp[v], dp[cur.to]);
		}
		else if (pnum != cur.num) {
			dp[v] = min(dp[v], d[cur.to]);
		}
	}
	if (pnum != -1 && dp[v] >= d[v]) {
		edges[2 * pnum].is_bridge = true; edges[2 * pnum + 1].is_bridge = true;
		bridges.push_back(pnum);
	}
}

void dfs2(int v, int cur_comp) {
	comp[v] = cur_comp;
	for (auto e : gr[v]) {
		Edge cur = edges[e];
		if (!cur.is_bridge && comp[cur.to] == -1) {
			dfs2(cur.to, cur_comp);
		}
		else if (comp[cur.to] != -1 && cur.is_bridge) {
			cgr[cur_comp].push_back(comp[cur.to]); cgr[comp[cur.to]].push_back(cur_comp);
		}
	}
}

void dfsts(int v) {
	vis[v] = true;
	if (parents[v] == v) {
		depth[v] = 0;
	}
	else {
		depth[v] = 1 + depth[parents[v]];
	}
	for (auto u : mp[v]) {
		if (!vis[u]) {
			parents[u] = v;
			dfsts(u);
		}
	}
	ts.push_back(v);
}

int Solve(int start, int turns) {
	//cout << "start and turns = " << start << " " << turns << endl;
	if (turns == 0) {
		return start;
	}
	if (turns == 1) {
		return bj[start][0];
	}
	int l = 0; int h = 30;
	while (l + 1 < h) {
		int m = (l + h) / 2;
		if ((1 << m) <= turns) {
			l = m;
		}
		else {
			h = m;
		}
	}
	//cout << "l = " << l << " " << bj[start][l] << endl;
	return Solve(bj[start][l], turns - (1 << l));
}

int LCA(int a, int b) {
	if (a == b) {
		return a;
	}
	if (bj[a][0] == bj[b][0]) {
		return bj[a][0];
	}
	int l = 0; int h = 17;
	while (l + 1 < h) {
		int m = (l + h) / 2;
		if (bj[a][m] == bj[b][m]) {
			h = m;
		}
		else {
			l = m;
		}
	}
	return LCA(bj[a][l], bj[b][l]);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	gr.resize(n); sol.assign(m, 'B'); d.resize(n); dp.resize(n);
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b; a--; b--;
		edges.push_back(Edge(a, b, i)); edges.push_back(Edge(b, a, i));
		gr[a].push_back(2 * i); gr[b].push_back(2 * i + 1);
	}

	used.assign(n, false);
	for (int i = 0; i < n; i++) {
		if (!used[i]) {
			dfs(i);
		}
	}

	//cout << "done dfs1" << endl;

	comp.resize(n, -1); int cur_comp = 0;
	for (int i = 0; i < n; i++) {
		if (comp[i] == -1) {
			cgr.push_back(vector<int>()); dfs2(i, cur_comp++);
		}
	}

	//cout << "done dfs2 " << endl;

	mp.resize(cur_comp);
	for (int bridge : bridges) {
		mp[comp[edges[2*bridge].from]].push_back(comp[edges[2*bridge].to]);
		mp[comp[edges[2*bridge].to]].push_back(comp[edges[2*bridge].from]);
		translate[{comp[edges[2 * bridge].from], comp[edges[2 * bridge].to]}] = { 'R', bridge };
		translate[{comp[edges[2 * bridge].to], comp[edges[2 * bridge].from]}] = { 'L', bridge };
	}

	vis.assign(cur_comp, false); parents.resize(cur_comp); depth.resize(cur_comp, INF);
	for (int i = 0; i < cur_comp; i++) {
		if (!vis[i]) {
			parents[i] = i; dfsts(i);
		}
	}

	bj.resize(cur_comp, vector<int>(18));
	for (int i = 0; i < cur_comp; i++) {
		bj[i][0] = parents[i];
	}

	for (int i = 1; i < 18; i++) {
		for (int j = 0; j < cur_comp; j++) {
			bj[j][i] == bj[bj[j][i - 1]][i - 1];
		}
	}

	//cout << "done dfs3" << endl;

	changesx.resize(cur_comp, -1); changesy.resize(cur_comp, -1);

	/*
	for (int i = 0; i < n; i++) {
		cout << "element " << i + 1 << " has component " << comp[i] << endl;
	}

	for (int i = 0; i < cur_comp; i++) {
		cout << "depth of comp " << i << " is " << depth[i] << endl;
	}
	*/

	cin >> p;
	for (int i = 0; i < p; i++) {
		int a, b; cin >> a >> b; a--; b--;
		//cout << "components " << comp[a] << " " << comp[b] << endl;
		int x = comp[a]; int y = comp[b];
		if (x != y) {
			//cout << "fine" << endl;
			//cout << "depths " << depth[x] << " " << depth[y] << endl;
			if (depth[x] < depth[y]) {
				y = Solve(y, depth[y] - depth[x]);
			}
			else if (depth[y] < depth[x]) {
				x = Solve(x, depth[x] - depth[y]);
			}
			//cout << "no issue" << endl;
			int lca = LCA(x, y); //cout << "lca for a, b = " << a + 1 << " " << b + 1 << " of component " << comp[a] << " " << comp[b] << " is " << lca << endl;
			if (changesx[comp[a]] == -1) {
				changesx[comp[a]] = lca;
			}
			else if (depth[lca] < depth[changesx[comp[a]]]) {
				changesx[comp[a]] = lca;
			}
			if (changesy[comp[b]] == -1){
				changesy[comp[b]] = lca;
			}
			else if (depth[lca] < depth[changesy[comp[b]]]) {
				changesy[comp[b]] = lca;
			}
		}
	}

	// now we need to do the changing

	for (int i = 0; i < cur_comp; i++) {
		//cout << "ts[i] and changes are " << ts[i] << " " << changesx[ts[i]] << " " << changesy[ts[i]] << endl;
		if (changesx[ts[i]] != -1) {
			if (depth[ts[i]] != depth[changesx[ts[i]]]) {
				sol[translate[{ts[i], parents[ts[i]]}].second] = translate[{ts[i], parents[ts[i]]}].first;
				if (changesx[parents[ts[i]]] == -1) {
					changesx[parents[ts[i]]] = changesx[ts[i]];
				}
				else if (depth[changesx[ts[i]]] < depth[changesx[parents[ts[i]]]]) {
					changesx[parents[ts[i]]] = changesx[ts[i]];
				}
			}
		}
		if (changesy[ts[i]] != -1) {
			if (depth[ts[i]] != depth[changesy[ts[i]]]) {
				sol[translate[{parents[ts[i]], ts[i]}].second] = translate[{parents[ts[i]], ts[i]}].first;
				if (changesy[parents[ts[i]]] == -1) {
					changesy[parents[ts[i]]] = changesy[ts[i]];
				}
				else if (depth[changesy[ts[i]]] < depth[changesy[parents[ts[i]]]]) {
					changesy[parents[ts[i]]] = changesy[ts[i]];
				}
			}
		}
	}

	//cout << "taken input " << endl;
	/*
	cout << "num components " << cur_comp << endl;
	for (int i = 0; i < n; i++) {
		cout << "comp " << i << " = " << comp[i] << endl;
	}
	*/

	

	for (int i = 0; i < sol.size(); i++) {
		cout << sol[i];
	}
	cout << "\n";


}


/*
for (int i = 0; i < cur_comp; i++) {
		//cout << "ts[" << i << "] = " << ts[i] << " with a parent of " << parents[ts[i]] << " with a count of " << x.count(ts[i]) << " for x and " << y.count(ts[i]) << " for y" << endl;
		//cout << "num occurentces " << x.count(ts[i]) << " " << y.count(ts[i]) << endl;
		int xcount = x.count(ts[i]); int ycount = y.count(ts[i]);
		for (int i = 0; i < min(xcount, ycount); i++) {
			//cout << "count2 " << x.count(ts[i]) << endl;
			auto ix = x.find(ts[i]); x.erase(ix);
			auto iy = y.find(ts[i]); y.erase(iy);
		}
		xcount = x.count(ts[i]); ycount = y.count(ts[i]);
		for (int i = 0; i < xcount; i++) {
			//cout << "count " << x.count(ts[i]) << endl;
			x.insert(parents[ts[i]]);
		}
		if (xcount > 0) {
			//cout << "i = " << i << " ts[i] = " << ts[i] << " and x.count(ts[i] = " << x.count(ts[i]) << endl;
			x.erase(ts[i]); sol[translate[{ts[i], parents[ts[i]]}].second] = translate[{ts[i], parents[ts[i]]}].first;
			//cout << "x changing " << translate[{ts[i], parents[ts[i]]}].second << " index to " << translate[{ts[i], parents[ts[i]]}].first << endl;
		}
		//cout << "occ of y " << y.count(ts[i]) << endl;
		for (int i = 0; i < ycount; i++) {
			//cout << "yoyoyo" << endl;
			y.insert(parents[ts[i]]); //cout << "adding " << endl;
		}
		if (ycount > 0) {
			//cout << "hello " << endl;
			y.erase(ts[i]); sol[translate[{parents[ts[i]], ts[i]}].second] = translate[{parents[ts[i]], ts[i]}].first;
			//cout << "y changing " << translate[{parents[ts[i]], ts[i]}].second << " index to " << translate[{parents[ts[i]], ts[i]}].first << endl;
		}
		//cout << "parents count of " << ts[i] << " " << x.count(parents[ts[i]]) << " " << y.count(parents[ts[i]]) << endl;
	}

	//cout << "part 4" << endl;


*/

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

oneway.cpp: In function 'int main()':
oneway.cpp:182:13: warning: value computed is not used [-Wunused-value]
  182 |    bj[j][i] == bj[bj[j][i - 1]][i - 1];
oneway.cpp:269:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  269 |  for (int i = 0; i < sol.size(); i++) {
      |                  ~~^~~~~~~~~~~~

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