oj.uz

Submission #197446

# Submission time Handle Problem Language Result Execution time Memory
197446 2020-01-21T09:27:44 Z quocnguyen1012 One-Way Streets (CEOI17_oneway) C++14
0 / 100
 11 ms 9976 KB 
#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 = 2e5 + 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];
int go[maxn];
 
void query (int u, int v, int direct){
	int p = par[u].fi, id = par[u].se;
	if (u == v) return;
	if (go[id] != 0 && go[id] != direct) {
		cout << "No";
		exit (0);
	}
	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';
	}
	go[id] = direct;
	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 >> P;
	for (int i=1; i<=M; ++i){
		cin >> U[i] >> V[i];
		adj[U[i]].pb (i); adj[V[i]].pb (i);
	}
	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);
	}
	cout << res;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:143: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:144: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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 9976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 9976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 9976 KB Output isn't correct
2 Halted 0 ms 0 KB -