oj.uz

Submission #650275

# Submission time Handle Problem Language Result Execution time Memory
650275 2022-10-13T10:14:51 Z drkarlicio2107 Traffic (CEOI11_tra) C++14
100 / 100
 1459 ms 63252 KB 
#include <bits/stdc++.h>
using namespace std;
pair <int, int> c [300010];
vector <int> g [300010];
vector <int> ob [300010];
vector <int> g2 [300010];
int comp [300010];
int vis [300010];
pair <int, int> dp [300010]; int vis2 [300010];
int sol [300010];
int ima [300010];
vector <int> kraj;
vector <int> pref;
int n, m, a, b; 
stack <int> s;
vector <pair <int, int> > out;
int ind=1;

void dfs (int x){
	vis [x]=1;
	for (int i=0; i<g [x].size(); i++){
		if (!vis [g[x][i]]) dfs (g [x][i]);
	}
	s.push (x);
	return ;
}

void dfs2 (int x){
	comp [x]=ind;
	for (int i=0; i<ob [x].size(); i++){
		if (!comp [ob[x][i]]) dfs2 (ob [x][i]);
	}
	return ;
}

void find_components (){
	for (int i=0; i<n; i++){
		if (!vis [i]){
			dfs (i);
		}
	}
	int sz=s.size();
	while (sz){
		int x=s.top();
		if (!comp [x]){
			dfs2 (x); ind++;
		}
		sz--;
		s.pop();
	}
	return ;
}

pair <int, int> rek (int x){
	if (vis2 [x]) return dp [x];
	vis2 [x]=1;
	for (int i=0; i<g2 [x].size(); i++) {
		pair <int, int> y=rek (g2 [x][i]);
		dp [x].first=min (dp [x].first, y.first);
		dp [x].second=max (dp [x].second, y.second);
	}
	return dp [x];
}

void dfs3 (int x){
	if (ima [x]) return ;
	ima [x]=1;
	for (int i=0; i<g [x].size(); i++) dfs3 (g [x][i]);
	return ;
}

int main(){
	cin >> n >> m >> a >> b;
	for (int i=0; i<n; i++) cin >> c [i].first >> c [i].second;
	for (int i=0; i<m; i++){
		int x, y, t; cin >> x >> y >> t; x--; y--;
		g [x].push_back (y); ob [y].push_back (x);
		if (t==2){
			g [y].push_back (x); ob [x].push_back (y);
		}
	}
	find_components ();
	
	//for (int i=0; i<n; i++) cout << comp [i] << " "; cout << endl;
	
	for (int i=0; i<n; i++){
		if (c [i].first==0) dfs3 (i);
		for (int j=0; j<g [i].size(); j++){
			if (comp [i]!=comp [g [i][j]]){
				g2 [comp [i]].push_back (comp [g [i][j]]);
			}
		}
	}
	for (int i=0; i<ind; i++){
		dp [i].first=1e9; dp [i].second=-1;
	}
	for (int i=0; i<n; i++){
		if (c [i].first==a){
			if (ima [i]) kraj.push_back (c [i].second);
			dp [comp [i]].first=min (dp [comp [i]].first, c [i].second);
			dp [comp [i]].second=max (dp [comp [i]].second, c [i].second);
		}
	}
	sort (kraj.begin(), kraj.end()); 
	for (int i=1; i<ind; i++){
		rek (i);
	}
	for (int i=1; i<ind; i++){
		if (dp [i].second==-1){
			sol [i]=0; continue;
		}
		vector<int>::iterator it=upper_bound (kraj.begin(), kraj.end(), dp [i].second); it--;
		vector<int>::iterator it2=lower_bound (kraj.begin(), kraj.end(), dp [i].first); it2--;
		int pos1=it-kraj.begin(); int pos2=it2-kraj.begin();
		//cout << pos1 << " " << pos2 << " " << dp [i].first << " " << dp [i].second << endl;
		sol [i]=pos1-pos2;
	}
	for (int i=0; i<n; i++){
		if (c [i].first==0) out.push_back ({c [i].second, sol [comp [i]]});
	}
	sort (out.rbegin(), out.rend());
	for (int i=0; i<out.size(); i++) cout << out [i].second << endl;
	return 0;
}

Compilation message

tra.cpp: In function 'void dfs(int)':
tra.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for (int i=0; i<g [x].size(); i++){
      |                ~^~~~~~~~~~~~~
tra.cpp: In function 'void dfs2(int)':
tra.cpp:30:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for (int i=0; i<ob [x].size(); i++){
      |                ~^~~~~~~~~~~~~~
tra.cpp: In function 'std::pair<int, int> rek(int)':
tra.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i=0; i<g2 [x].size(); i++) {
      |                ~^~~~~~~~~~~~~~
tra.cpp: In function 'void dfs3(int)':
tra.cpp:68:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for (int i=0; i<g [x].size(); i++) dfs3 (g [x][i]);
      |                ~^~~~~~~~~~~~~
tra.cpp: In function 'int main()':
tra.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for (int j=0; j<g [i].size(); j++){
      |                 ~^~~~~~~~~~~~~
tra.cpp:122:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |  for (int i=0; i<out.size(); i++) cout << out [i].second << endl;
      |                ~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21460 KB Output is correct
2 Correct 14 ms 21460 KB Output is correct
3 Correct 12 ms 21460 KB Output is correct
4 Correct 11 ms 21460 KB Output is correct
5 Correct 11 ms 21460 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 12 ms 21460 KB Output is correct
3 Correct 11 ms 21460 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21400 KB Output is correct
2 Correct 13 ms 21496 KB Output is correct
3 Correct 14 ms 21456 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 21664 KB Output is correct
2 Correct 21 ms 22228 KB Output is correct
3 Correct 18 ms 21896 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 23764 KB Output is correct
2 Correct 129 ms 27780 KB Output is correct
3 Correct 64 ms 24792 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 25488 KB Output is correct
2 Correct 173 ms 29424 KB Output is correct
3 Correct 100 ms 27772 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 29748 KB Output is correct
2 Correct 280 ms 36312 KB Output is correct
3 Correct 372 ms 32040 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 30268 KB Output is correct
2 Correct 270 ms 34176 KB Output is correct
3 Correct 391 ms 32184 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 36736 KB Output is correct
2 Correct 533 ms 43984 KB Output is correct
3 Correct 797 ms 41416 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 46796 KB Output is correct
2 Correct 885 ms 57660 KB Output is correct
3 Correct 789 ms 45248 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1315 ms 52376 KB Output is correct
2 Correct 960 ms 59104 KB Output is correct
3 Correct 1412 ms 52224 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 40692 KB Output is correct
2 Correct 983 ms 63252 KB Output is correct
3 Correct 1216 ms 53408 KB Output is correct
4 Correct 1459 ms 59220 KB Output is correct