oj.uz

Submission #43264

# Submission time Handle Problem Language Result Execution time Memory
43264 2018-03-12T04:41:37 Z ffresh 버스 (JOI14_bus) C++14
100 / 100
 322 ms 242500 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, 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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3832 KB Output is correct
2 Correct 4 ms 3936 KB Output is correct
3 Correct 4 ms 3988 KB Output is correct
4 Correct 4 ms 3988 KB Output is correct
5 Correct 4 ms 3988 KB Output is correct
6 Correct 4 ms 4088 KB Output is correct
7 Correct 4 ms 4088 KB Output is correct
8 Correct 5 ms 4148 KB Output is correct
9 Correct 4 ms 4148 KB Output is correct
10 Correct 4 ms 4188 KB Output is correct
11 Correct 5 ms 4204 KB Output is correct
12 Correct 5 ms 4204 KB Output is correct
13 Correct 5 ms 4332 KB Output is correct
14 Correct 6 ms 4332 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4332 KB Output is correct
2 Correct 36 ms 4832 KB Output is correct
3 Correct 36 ms 4860 KB Output is correct
4 Correct 8 ms 4860 KB Output is correct
5 Correct 8 ms 4860 KB Output is correct
6 Correct 6 ms 4860 KB Output is correct
7 Correct 26 ms 4860 KB Output is correct
8 Correct 4 ms 4860 KB Output is correct
9 Correct 28 ms 4860 KB Output is correct
10 Correct 40 ms 4908 KB Output is correct
11 Correct 33 ms 4908 KB Output is correct
12 Correct 43 ms 5164 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 13764 KB Output is correct
2 Correct 248 ms 13820 KB Output is correct
3 Correct 255 ms 22780 KB Output is correct
4 Correct 243 ms 31228 KB Output is correct
5 Correct 264 ms 39808 KB Output is correct
6 Correct 246 ms 48472 KB Output is correct
7 Correct 214 ms 55744 KB Output is correct
8 Correct 276 ms 65068 KB Output is correct
9 Correct 242 ms 73820 KB Output is correct
10 Correct 202 ms 80824 KB Output is correct
11 Correct 199 ms 88320 KB Output is correct
12 Correct 218 ms 95608 KB Output is correct
13 Correct 224 ms 103208 KB Output is correct
14 Correct 195 ms 110424 KB Output is correct
15 Correct 224 ms 117944 KB Output is correct
16 Correct 129 ms 120616 KB Output is correct
17 Correct 96 ms 123048 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 123896 KB Output is correct
2 Correct 286 ms 123896 KB Output is correct
3 Correct 277 ms 133524 KB Output is correct
4 Correct 322 ms 143284 KB Output is correct
5 Correct 285 ms 152344 KB Output is correct
6 Correct 312 ms 162008 KB Output is correct
7 Correct 262 ms 170304 KB Output is correct
8 Correct 319 ms 180636 KB Output is correct
9 Correct 308 ms 190248 KB Output is correct
10 Correct 244 ms 198040 KB Output is correct
11 Correct 224 ms 206360 KB Output is correct
12 Correct 222 ms 214784 KB Output is correct
13 Correct 230 ms 222932 KB Output is correct
14 Correct 233 ms 231180 KB Output is correct
15 Correct 227 ms 239508 KB Output is correct
16 Correct 125 ms 242500 KB Output is correct