Submission #650275

#	Time	Username	Problem	Language	Result	Execution time	Memory
650275		drkarlicio2107	Traffic (CEOI11_tra)	C++14	100 / 100	1459 ms	63252 KiB

tra

#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 (stderr)

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 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9