oj.uz

Submission #287454

# Submission time Handle Problem Language Result Execution time Memory
287454 2020-08-31T17:07:45 Z Namnamseo Traffic (CEOI11_tra) C++17
100 / 100
 1436 ms 61212 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
void read(int& x){ scanf("%d",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define x first
#define y second
const int inf=1e9;
#define data Data

int n, A, B;

pp data[300010];
vector<int> ed[300010];
vector<int> re[300010];

void in(){
	int m;
	read(n, m, A, B);
	for(int i=1; i<=n; ++i){
		int x, y; read(x, y);
		data[i] = {x, y};
	}
	for(;m--;){
		int f, t, k;
		read(f, t, k);
		ed[f].pb(t);
		re[t].pb(f);
		if(k != 1) ed[t].pb(f), re[f].pb(t);
	}
}

vector<int> right;
int miny[300010];
int maxy[300010];

bool vis[300010];

void bfs(){
	queue<int> q;
	for(int i=1; i<=n; ++i) if(data[i].x == 0) q.push(i), vis[i]=1;
	while(q.size()){
		int x=q.front(); q.pop();
		for(int y:ed[x]){
			if(!vis[y]) vis[y]=1, q.push(y);
		}
	}
}

void sep(){
	fill(miny+1, miny+n+1, inf);
	fill(maxy+1, maxy+n+1, -inf);
	vector<int> ys;
	for(int i=1; i<=n; ++i) if(data[i].x == A && vis[i]) ys.pb(data[i].y);
	sort(all(ys)); ys.erase(unique(all(ys)), ys.end());
	for(int i=1; i<=n; ++i) if(data[i].x == A && vis[i]){
		miny[i] = maxy[i] = lower_bound(all(ys), data[i].y) - ys.begin();
	}
}

void dijk(){
	priority_queue<pp> pq;
	for(int i=1; i<=n; ++i) if(data[i].x == A){
		pq.push(pp{-miny[i], i});
	}
	while(pq.size()){
		int d, i; tie(d, i) = pq.top(); pq.pop(); d=-d;
		if(d != miny[i]) continue;
		for(int y:re[i]) if(miny[y] > d){
			miny[y]=d;
			pq.push(pp{-miny[y], y});
		}
	}
	
	for(int i=1; i<=n; ++i) if(data[i].x == A){
		pq.push(pp{maxy[i], i});
	}
	while(pq.size()){
		int d, i; tie(d, i) = pq.top(); pq.pop();
		if(d != maxy[i]) continue;
		for(int y:re[i]) if(maxy[y] < d){
			maxy[y]=d;
			pq.push(pp{maxy[y], y});
		}
	}
}

int main()
{
    in(); bfs(); sep(); dijk();
    vector<pp> ans;
    for(int i=1; i<=n; ++i) if(data[i].x == 0){
		if(maxy[i] == -inf) maxy[i]=0, miny[i]=1;
		ans.pb(pp{data[i].y, maxy[i] - miny[i] + 1});
    }
    sort(all(ans)); reverse(all(ans));
    for(auto tmp:ans) printf("%d\n", tmp.second);
    return 0;
}

Compilation message

tra.cpp: In function 'void read(int&)':
tra.cpp:5:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    5 | void read(int& x){ scanf("%d",&x); }
      |                    ~~~~~^~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14552 KB Output is correct
2 Correct 16 ms 14976 KB Output is correct
3 Correct 15 ms 14856 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16120 KB Output is correct
2 Correct 124 ms 19544 KB Output is correct
3 Correct 64 ms 17144 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 18552 KB Output is correct
2 Correct 125 ms 20944 KB Output is correct
3 Correct 71 ms 19576 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 22448 KB Output is correct
2 Correct 219 ms 25092 KB Output is correct
3 Correct 308 ms 27056 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 25208 KB Output is correct
2 Correct 286 ms 25124 KB Output is correct
3 Correct 314 ms 27896 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 31096 KB Output is correct
2 Correct 410 ms 33396 KB Output is correct
3 Correct 647 ms 39020 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 40692 KB Output is correct
2 Correct 734 ms 45892 KB Output is correct
3 Correct 709 ms 40560 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1260 ms 57980 KB Output is correct
2 Correct 787 ms 46944 KB Output is correct
3 Correct 1073 ms 56440 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 32892 KB Output is correct
2 Correct 801 ms 48472 KB Output is correct
3 Correct 955 ms 51236 KB Output is correct
4 Correct 1436 ms 61212 KB Output is correct