oj.uz

Submission #595493

# Submission time Handle Problem Language Result Execution time Memory
595493 2022-07-13T19:07:42 Z Hacv16 Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 48844 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 2e6 + 15;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

#define pb push_back
#define sz(x) (int) x.size()
#define fr first
#define sc second
#define mp make_pair
#define all(x) x.begin(), x.end()
#define dbg(x) cout << #x << ": " << "[ " << x << " ]\n"

int n, q, d[MAX], seen[MAX], c[MAX], nx[MAX];
vector<int> adj[MAX];

struct event{
	int s, e, id;
} ev[MAX];

bool f(event a, event b){ //can i do a --> b ?
	return b.s <= a.e && a.e <= b.e;
}

bool cmp(event& a, event& b) {
	if(a.e != b.e) return a.e < b.e;
	return a.s < b.s;
}

void dfs(int u, int col, int h){
	seen[u] = true;
	c[u] = col, d[u] = h;
	
	if(nx[u] != 0) 
		dfs(nx[u], col, h + 1);
}

void solve1(){
	for(int i = 1; i <= n; i++){
    	cin >> ev[i].s >> ev[i].e;
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(i == j) continue;
			
			if(f(ev[i], ev[j])) adj[i].pb(j);
		}
	}
	
	while(q--){
		int s, e; cin >> s >> e;
		
		queue<int> q;
		vector<int> dist(n + 1, -1);
		
		q.push(s); dist[s] = 0;
		
		while(q.size()){
			int u = q.front();
			q.pop();
			
			for(auto v : adj[u]){
				if(dist[v] == -1){
					dist[v] = dist[u] + 1;
					q.push(v);
				}
			}
		}
		
		if(dist[e] == -1) cout << "impossible" << '\n';
		else cout << dist[e] << '\n';
	}
}

void solve2(){	
	for(int i = 1; i <= n; i++){
		cin >> ev[i].s >> ev[i].e;
		ev[i].id = i;
	}	        
	
	sort(ev + 1, ev + 1 + n, cmp);
	
	for(int i = 1, j = 2; i <= n; i++){
		while(j <= n && !f(ev[i], ev[j])) j++;
		if(j == n + 1) break;
		nx[ev[i].id] = ev[j].id;
	}
	
	for(int i = 1, c = 1; i <= n; i++){
		if(!seen[ev[i].id]) dfs(ev[i].id, c++, 1);
	}
	
	while(q--){
		int u, v; cin >> u >> v;
		
		if(c[u] != c[v] || (c[u] == c[v] && d[v] <= d[u])) cout << "impossible" << '\n';
		else cout << abs(d[u] - d[v]) << '\n';
	}
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 

    cin >> n >> q;
    
	solve2();
	
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1595 ms 47316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1598 ms 47316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1598 ms 47316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1598 ms 47316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1589 ms 48844 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1595 ms 47316 KB Time limit exceeded
2 Halted 0 ms 0 KB -