oj.uz

Submission #115657

# Submission time Handle Problem Language Result Execution time Memory
115657 2019-06-08T13:31:47 Z 김세빈(#2868) Traffic (CEOI11_tra) C++14
100 / 100
 1016 ms 50952 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

vector <pii> L, R;
queue <int> Q;
vector <int> V[303030], G[303030], S;
pii dp[303030];
int scc[303030], N[303030];
int chk1[303030], chk2[303030], chk3[303030], chk4[303030];
int n, m, g, cnt;

int dfs(int p)
{
	int ret = ++cnt;
	
	chk3[p] = 1; N[p] = cnt;
	S.push_back(p);
	
	for(int &t: V[p]){
		if(!chk3[t]) ret = min(ret, dfs(t));
		else if(!scc[t]) ret = min(ret, N[t]);
	}
	
	if(ret == N[p]){
		for(++g; !scc[p]; S.pop_back()){
			scc[S.back()] = g;
		}
	}
	
	return ret;
}

pii f(int p)
{
	if(chk4[p]) return dp[p];
	
	int l, r;
	
	for(int &t: G[p]){
		tie(l, r) = f(t);
		dp[p].first = min(dp[p].first, l);
		dp[p].second = max(dp[p].second, r);
	}
	
	chk4[p] = 1;
	return dp[p];
}

int main()
{
	int i, x, y, a, b, u, v, t, p, l, r;
	
	scanf("%d%d%d%d", &n, &m, &a, &b);
	
	for(i=1; i<=n; i++){
		scanf("%d%d", &x, &y);
		if(x == 0){
			L.emplace_back(y, i);
			Q.push(i); chk1[i] = 1;
		}
		else if(x == a){
			R.emplace_back(y, i);
			chk2[i] = 1;
		}
	}
	
	sort(L.rbegin(), L.rend());
	
	for(i=1; i<=m; i++){
		scanf("%d%d%d", &u, &v, &t);
		if(t == 1) V[u].push_back(v);
		else{
			V[u].push_back(v);
			V[v].push_back(u);
		}
	}
	
	for(; !Q.empty(); ){
		p = Q.front(); Q.pop();
		if(chk2[p]) chk2[p] ++;
		for(int &q: V[p]){
			if(!chk1[q]){
				chk1[q] = 1;
				Q.push(q);
			}
		}
	}
	
	for(i=0; i<R.size(); ){
		if(chk2[R[i].second] == 1){
			swap(R[i], R.back()); R.pop_back();
		}
		else i ++;
	}
	
	for(i=1; i<=n; i++){
		chk2[i] = 0;
	}
	
	sort(R.begin(), R.end());
	
	for(i=1; i<=n; i++){
		if(!chk3[i]) dfs(i);
	}
	
	for(i=1; i<=g; i++){
		dp[i] = pii(R.size() - 1, 0);
	}
	
	for(i=1; i<=n; i++){
		for(int &q: V[i]){
			if(scc[i] != scc[q]){
				G[scc[i]].push_back(scc[q]);
			}
		}
	}
	
	for(i=0; i<R.size(); i++){
		dp[scc[R[i].second]].first = min(dp[scc[R[i].second]].first, i);
		dp[scc[R[i].second]].second = max(dp[scc[R[i].second]].second, i);
	}
	
	for(i=0; i<L.size(); i++){
		tie(l, r) = f(scc[L[i].second]);
		if(l <= r) printf("%d\n", r - l + 1);
		else printf("0\n");
	}
	
	return 0;
}

Compilation message

tra.cpp: In function 'int main()':
tra.cpp:92:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<R.size(); ){
           ~^~~~~~~~~
tra.cpp:121:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<R.size(); i++){
           ~^~~~~~~~~
tra.cpp:126:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<L.size(); i++){
           ~^~~~~~~~~
tra.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &n, &m, &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
tra.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~
tra.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14592 KB Output is correct
2 Correct 14 ms 14592 KB Output is correct
3 Correct 14 ms 14592 KB Output is correct
4 Correct 13 ms 14592 KB Output is correct
5 Correct 13 ms 14592 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14592 KB Output is correct
2 Correct 14 ms 14592 KB Output is correct
3 Correct 14 ms 14592 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14592 KB Output is correct
2 Correct 14 ms 14720 KB Output is correct
3 Correct 13 ms 14592 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14720 KB Output is correct
2 Correct 18 ms 15104 KB Output is correct
3 Correct 18 ms 14976 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 16768 KB Output is correct
2 Correct 70 ms 20172 KB Output is correct
3 Correct 43 ms 16760 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 17404 KB Output is correct
2 Correct 81 ms 19568 KB Output is correct
3 Correct 60 ms 19064 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 20860 KB Output is correct
2 Correct 159 ms 24428 KB Output is correct
3 Correct 223 ms 21688 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 20504 KB Output is correct
2 Correct 162 ms 23040 KB Output is correct
3 Correct 206 ms 21844 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 25240 KB Output is correct
2 Correct 287 ms 31408 KB Output is correct
3 Correct 432 ms 28152 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 38416 KB Output is correct
2 Correct 514 ms 46656 KB Output is correct
3 Correct 486 ms 37368 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1016 ms 40028 KB Output is correct
2 Correct 564 ms 47588 KB Output is correct
3 Correct 891 ms 35616 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 34368 KB Output is correct
2 Correct 598 ms 50952 KB Output is correct
3 Correct 767 ms 43372 KB Output is correct
4 Correct 868 ms 41320 KB Output is correct