Submission #43264

#	Time	Username	Problem	Language	Result	Execution time	Memory
43264		ffresh	버스 (JOI14_bus)	C++14	100 / 100	322 ms	242500 KiB

bus

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+15, M =3e5+5;


int a[M],b[M],x[M],y[M];
vector<pair<int,int> > adj[N];


int mini[M];


void dfs(int root,int T,int R){

	int u,i,id;

	while(!adj[root].empty()){
		id= adj[root].back().second;

		if(adj[root].back().first<=T){
			adj[root].pop_back();
		}
		else
			break;
		mini[id] = R;
		dfs(a[id]^b[id]^root,x[id],R);
	}
}

int R[N],X[N];
int main(){
	//freopen("input.txt","r",stdin);

	int n,m;
	cin>>n>>m;
	memset(mini,-1,sizeof(mini));
	vector<pair<int,int> >edge;
	for(int i=0;i<m;++i){
		scanf("%d%d%d%d",&a[i],&b[i],&x[i],&y[i]);
		if(b[i]!= n)
			adj[b[i]].push_back(make_pair(y[i],i));
		else{
			edge.push_back(make_pair(y[i],i));
			
			if(a[i]==1)
				mini[i]= y[i];
		}
	}
	
	sort(edge.begin(),edge.end());

	for(int i=1;i<=n;++i){
		sort(adj[i].begin(),adj[i].end());
		reverse(adj[i].begin(),adj[i].end());
	}
	for(int i=0;i<edge.size();++i){
		int id = edge[i].second;
		dfs(a[id],x[id],y[id]);
	}
	edge.clear();
	for(int i=0;i<m;++i){
		if(a[i]==1 && mini[i]!=-1){
			edge.push_back(make_pair(mini[i],x[i]));
		}
	}
	int pos=1;
	for(int i=0;i<edge.size();++i){
		X[pos++]= edge[i].first;
	}

	sort(X+1,X+pos);

	pos = unique(X+1,X+pos)- X;

	R[0]= -1;
	int id;
	for(int i=0;i<edge.size();++i){
		id = lower_bound(X+1,X+pos, edge[i].first)- X;
		assert(X[id]== edge[i].first);
		R[id]= max(R[id],edge[i].second);
	}
	for(int i=1;i<=pos;++i)
		R[i] = max(R[i],R[i-1]);

	int q,l;
	cin>>q;
	for(int i=0;i<q;++i){
		scanf("%d",&l);
		id = lower_bound(X+1,X+pos, l+1)- X-1;
		printf("%d\n",R[id]);
	}
}

Compilation message (stderr)

bus.cpp: In function 'void dfs(int, int, int)':
bus.cpp:17:6: warning: unused variable 'u' [-Wunused-variable]
  int u,i,id;
      ^
bus.cpp:17:8: warning: unused variable 'i' [-Wunused-variable]
  int u,i,id;
        ^
bus.cpp: In function 'int main()':
bus.cpp:58:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<edge.size();++i){
               ^
bus.cpp:69:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<edge.size();++i){
               ^
bus.cpp:79:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<edge.size();++i){
               ^
bus.cpp:41:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d",&a[i],&b[i],&x[i],&y[i]);
                                            ^
bus.cpp:90:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&l);
                 ^

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50