oj.uz

Submission #43263

# Submission time Handle Problem Language Result Execution time Memory
43263 2018-03-12T04:37:45 Z ffresh 버스 (JOI14_bus) C++14
0 / 100
 293 ms 32292 KB 
#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+1, edge[i].first)- X;
		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+1, l+1)- X-1;
		printf("%d\n",R[id]);
	}
}

Compilation message

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:76: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:86:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&l);
                 ^

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3832 KB Output is correct
2 Incorrect 5 ms 3940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4008 KB Output is correct
2 Correct 41 ms 4848 KB Output is correct
3 Correct 42 ms 4848 KB Output is correct
4 Correct 8 ms 4848 KB Output is correct
5 Correct 8 ms 4848 KB Output is correct
6 Correct 7 ms 4848 KB Output is correct
7 Incorrect 28 ms 4848 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 13804 KB Output is correct
2 Incorrect 265 ms 22612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 23176 KB Output is correct
2 Incorrect 290 ms 32292 KB Output isn't correct
3 Halted 0 ms 0 KB -