oj.uz

Submission #45293

# Submission time Handle Problem Language Result Execution time Memory
45293 2018-04-12T15:39:48 Z bugmenot111 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 386 ms 126696 KB 
/*
if an edge is not a bridge it can be oriented either way;
the orientation of the bridges is uniquely determined;
let's call the input pairs "required pairs";
for each bridge B:
if there is no required pair with a node from the first component of the graph and the second component of the graph:
B can be oriented either way
otherwise: orient B the same way as the required pair from component A to component B
obviously, there cannot be two required pairs with different orientations because there can be no solution!
Algorithm: 
	Build "bridge tree" T of G
	For every pair going from comp(u) to comp(v) in T:
		orient all edges from comp(u) to LCA(comp(u), comp(v)) upwards
		orient all edges from LCA(comp(u), comp(v)) to comp(v) downwards
	The loop can be optimized by using a version of the difference array on the tree.
*/
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <queue>
#define MAXN 100100
typedef std::vector< std::pair<int, int> > edge_list;
typedef std::vector< std::vector<int> > graph;
typedef std::vector< std::vector< std::pair<int, int> > > labeled_edge_graph;
struct bridge_tree {
	static const int N = 100100;
	static const int M = 100100;
    std::vector<int> g[N];int U[M],V[M];  //edge list representation of the graph. 
    bool isbridge[M]; // if i'th edge is a bridge edge or not 
    int visited[N];int arr[N],T; //supporting arrays
    int cmpno = 1;
    std::queue<int> Q[N];
     
    int adj(int u,int e){
        return U[e]==u?V[e]:U[e];
    }
    int dfs0(int u,int edge)    //marks all the bridges
    {
        visited[u]=1;
        arr[u]=T++;
        int dbe = arr[u];
        for(int i=0;i<(int)g[u].size();i++)
        {
            int e = g[u][i];
            int w = adj(u,e);
            if(!visited[w])
                dbe = std::min(dbe,dfs0(w,e));
            else if(e!=edge)
                dbe = std::min(dbe,arr[w]);
        }
        if(dbe == arr[u] && edge!=-1)
            isbridge[edge]=true;
        return dbe;
    }
     
    void dfs1(int v) //Builds the tree with each edge a bridge from original graph
    {
        int currcmp = cmpno;    // current component no.
        Q[currcmp].push(v);    // A different queue for each component, coz   during bfs we shall go to another component (step of dfs) and then come   back to this one and continue our bfs
        visited[v]=currcmp;
        while(!Q[currcmp].empty())    //bfs. Exploring all nodes of this  component
        {
            int u = Q[currcmp].front();    
            Q[currcmp].pop();    
            for(int i=0;i<(int)g[u].size();i++)
            {
                int e = g[u][i];
                int w = adj(u,e);
                if(visited[w])continue;
                //if the edge under consideration is bridge and
                //other side is not yet explored, go there (step of dfs)
                if(isbridge[e])
                {
                    cmpno++;
                    dfs1(w);
                }
                else     //else continue with our bfs
                {
                    Q[currcmp].push(w);
                    visited[w]=currcmp;
                }
            }
        }
    }
};
std::vector<int> label_vertices(const int n, const int m, const edge_list& el) {
	static struct bridge_tree bt;
	std::vector<int> ans(n);
	for(int i = 0; i < m; i++) bt.U[i] = el[i].first, bt.V[i] = el[i].second;
	for(int i = 0; i < m; i++) bt.g[bt.U[i]].push_back(i);
	for(int i = 0; i < m; i++) bt.g[bt.V[i]].push_back(i);
	for(int i = 0; i < m; i++) if(!bt.visited[i]) bt.dfs0(i, -1);
	std::memset(bt.visited, 0, sizeof(bt.visited));
	for(int i = 0; i < n; i++) if(!bt.visited[i]) bt.dfs1(i);
	for(int i = 0; i < n; i++) ans[i] = bt.visited[i] - 1;
	return ans;
}
std::vector<std::pair<int, int>> tree[MAXN];
struct f2lk_dsu {
	int par[MAXN];
	int rnk[MAXN];
	int find(int x) {
		return par[x] == x ? x : par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if(x == y) return;
		if(rnk[x] > rnk[y]) par[y] = x;
		else if(rnk[x] < rnk[y]) par[x] = y;
		else if(rnk[x] == rnk[y]) rnk[par[y] = x]++;
	}
	f2lk_dsu() {
		std::iota(par, par + MAXN, 0);
	}
};
void offline_lca_aux(std::vector<int>& lc, edge_list* qr, int u, int p = -1) {
	static f2lk_dsu d;
	static int ancestor[MAXN];
	static bool black[MAXN];
	if(black[u] == true) return;
	ancestor[u] = u;
	for(const auto& pa: tree[u]) {
		int v = pa.first;
		if(v == p) continue;
		offline_lca_aux(lc, qr, v, u);
		d.unite(u, v);
		ancestor[d.find(u)] = u;
	}
	black[u] = true;
	for(const auto& p: qr[u]) 
		if(black[p.first]) lc[p.second] = ancestor[d.find(p.first)];
}
std::vector<int> offline_lca(const int n, const edge_list& queries) {
	static edge_list qr[MAXN];
	std::vector<int> lc(queries.size());
	for(int i = 0; i < queries.size(); i++) {
		auto p = queries[i];
		qr[p.first].push_back({p.second, i});
		qr[p.second].push_back({p.first, i});
	}
	for(int i = 0; i < n; i++) offline_lca_aux(lc, qr, i);
	return lc;
}
void dfs(int* up_edges, int* down_edges, std::string& ans, const std::vector<int>& lab, const edge_list& el, int v = 0, int p = -1) {
	static bool visited[MAXN];
	if(visited[v]) return;
	visited[v] = true;
	for(const auto& c: tree[v])
		if(c.first != p) dfs(up_edges, down_edges, ans, lab, el, c.first, v);
	for(const auto& c: tree[v])
		if(c.first != p) up_edges[v] += up_edges[c.first], down_edges[v] += down_edges[c.first];
	for(const auto& c: tree[v])
		if(c.first == p) {
			if(up_edges[v] == 0 && down_edges[v] > 0) ans[c.second] = lab[el[c.second].first] == p ? 'R' : 'L';
			if(up_edges[v] > 0 && down_edges[v] == 0) ans[c.second] = lab[el[c.second].first] == p ? 'L' : 'R';
		}
}
std::string solve(const int n, const int m, const int p, const edge_list& el, const edge_list& pairs) {
	static int up_edges[MAXN];
	static int down_edges[MAXN];
	static std::string ans(m, 'B');
	edge_list p2(pairs);
	auto lab = label_vertices(n, m, el); // build bridge-block tree
	int n2 = *std::max_element(lab.begin(), lab.end());
	for(int i = 0; i < m; i++) {
		int x = lab[el[i].first];
		int y = lab[el[i].second];
		if(x != y) {
			tree[x].push_back({y, i});
			tree[y].push_back({x, i});
		}
	}
	for(auto& p: p2)
		p = {lab[p.first], lab[p.second]};
	p2.erase(std::remove_if(p2.begin(), p2.end(), [](std::pair<int, int> p){return p.first == p.second;}), p2.end());
	std::sort(p2.begin(), p2.end());
	p2.erase(std::unique(p2.begin(), p2.end()), p2.end());
	auto lc = offline_lca(n2, p2);
	for(int i = 0; i < p2.size(); i++) {
		int x = p2[i].first;
		int y = p2[i].second;
		int l = lc[i];
		up_edges[x]++;
		up_edges[l]--;
		down_edges[y]++;
		down_edges[l]--;
	}
	for(int i = 0; i < n2; i++) dfs(up_edges, down_edges, ans, lab, el);
	return ans;
}
int main(void) {
	int n, m, p;
	scanf("%d%d", &n, &m);
	edge_list edges(m);
	for(int i = 0; i < m; i++) {
		int x;
		int y;
		scanf("%d%d", &x, &y);
		edges[i] = {x - 1, y - 1};
	}
	scanf("%d", &p);
	edge_list pairs(p);
	for(int i = 0; i < p; i++) {
		int x;
		int y;
		scanf("%d%d", &x, &y);
		pairs[i] = {x - 1, y - 1};
	}
	puts(solve(n, m, p, edges, pairs).c_str());
	return 0;
}

Compilation message

oneway.cpp: In function 'std::vector<int> offline_lca(int, const edge_list&)':
oneway.cpp:143:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < queries.size(); i++) {
                 ~~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'std::__cxx11::string solve(int, int, int, const edge_list&, const edge_list&)':
oneway.cpp:186:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < p2.size(); i++) {
                 ~~^~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:200:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:205:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:208:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &p);
  ~~~~~^~~~~~~~~~
oneway.cpp:213:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 75640 KB Output is correct
2 Correct 69 ms 75744 KB Output is correct
3 Correct 72 ms 75744 KB Output is correct
4 Correct 70 ms 75984 KB Output is correct
5 Correct 71 ms 75984 KB Output is correct
6 Correct 70 ms 75984 KB Output is correct
7 Correct 68 ms 75984 KB Output is correct
8 Correct 69 ms 76016 KB Output is correct
9 Correct 79 ms 76016 KB Output is correct
10 Correct 75 ms 76016 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 75640 KB Output is correct
2 Correct 69 ms 75744 KB Output is correct
3 Correct 72 ms 75744 KB Output is correct
4 Correct 70 ms 75984 KB Output is correct
5 Correct 71 ms 75984 KB Output is correct
6 Correct 70 ms 75984 KB Output is correct
7 Correct 68 ms 75984 KB Output is correct
8 Correct 69 ms 76016 KB Output is correct
9 Correct 79 ms 76016 KB Output is correct
10 Correct 75 ms 76016 KB Output is correct
11 Correct 130 ms 81844 KB Output is correct
12 Correct 137 ms 83920 KB Output is correct
13 Correct 177 ms 85588 KB Output is correct
14 Correct 170 ms 88272 KB Output is correct
15 Correct 184 ms 89868 KB Output is correct
16 Correct 226 ms 94056 KB Output is correct
17 Correct 209 ms 98028 KB Output is correct
18 Correct 218 ms 98028 KB Output is correct
19 Correct 187 ms 102356 KB Output is correct
20 Correct 144 ms 102356 KB Output is correct
21 Correct 136 ms 102356 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 75640 KB Output is correct
2 Correct 69 ms 75744 KB Output is correct
3 Correct 72 ms 75744 KB Output is correct
4 Correct 70 ms 75984 KB Output is correct
5 Correct 71 ms 75984 KB Output is correct
6 Correct 70 ms 75984 KB Output is correct
7 Correct 68 ms 75984 KB Output is correct
8 Correct 69 ms 76016 KB Output is correct
9 Correct 79 ms 76016 KB Output is correct
10 Correct 75 ms 76016 KB Output is correct
11 Correct 130 ms 81844 KB Output is correct
12 Correct 137 ms 83920 KB Output is correct
13 Correct 177 ms 85588 KB Output is correct
14 Correct 170 ms 88272 KB Output is correct
15 Correct 184 ms 89868 KB Output is correct
16 Correct 226 ms 94056 KB Output is correct
17 Correct 209 ms 98028 KB Output is correct
18 Correct 218 ms 98028 KB Output is correct
19 Correct 187 ms 102356 KB Output is correct
20 Correct 144 ms 102356 KB Output is correct
21 Correct 136 ms 102356 KB Output is correct
22 Correct 287 ms 110268 KB Output is correct
23 Correct 286 ms 110268 KB Output is correct
24 Correct 386 ms 112128 KB Output is correct
25 Correct 281 ms 122568 KB Output is correct
26 Correct 276 ms 122568 KB Output is correct
27 Correct 299 ms 122568 KB Output is correct
28 Correct 123 ms 122568 KB Output is correct
29 Correct 166 ms 122568 KB Output is correct
30 Correct 170 ms 122568 KB Output is correct
31 Correct 166 ms 122568 KB Output is correct
32 Correct 231 ms 126696 KB Output is correct