oj.uz

Submission #595492

# Submission time Handle Problem Language Result Execution time Memory
595492 2022-07-13T19:06:56 Z Hacv16 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 51340 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;
    
	if(n <= 1000 && q <= 100) solve1();
	else solve2();
	
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Execution timed out 1578 ms 49228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Correct 21 ms 47196 KB Output is correct
3 Correct 30 ms 47248 KB Output is correct
4 Correct 29 ms 47284 KB Output is correct
5 Correct 28 ms 47316 KB Output is correct
6 Correct 35 ms 48204 KB Output is correct
7 Correct 43 ms 48852 KB Output is correct
8 Correct 42 ms 49996 KB Output is correct
9 Correct 107 ms 51284 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Correct 21 ms 47196 KB Output is correct
3 Correct 30 ms 47248 KB Output is correct
4 Correct 29 ms 47284 KB Output is correct
5 Correct 28 ms 47316 KB Output is correct
6 Correct 35 ms 48204 KB Output is correct
7 Correct 43 ms 48852 KB Output is correct
8 Correct 42 ms 49996 KB Output is correct
9 Correct 107 ms 51284 KB Output is correct
10 Correct 28 ms 47188 KB Output is correct
11 Correct 25 ms 47188 KB Output is correct
12 Correct 31 ms 47260 KB Output is correct
13 Correct 29 ms 47284 KB Output is correct
14 Correct 31 ms 47304 KB Output is correct
15 Correct 35 ms 48088 KB Output is correct
16 Correct 42 ms 48948 KB Output is correct
17 Correct 44 ms 49904 KB Output is correct
18 Correct 99 ms 51340 KB Output is correct
19 Execution timed out 1571 ms 47456 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Correct 21 ms 47196 KB Output is correct
3 Correct 30 ms 47248 KB Output is correct
4 Correct 29 ms 47284 KB Output is correct
5 Correct 28 ms 47316 KB Output is correct
6 Correct 35 ms 48204 KB Output is correct
7 Correct 43 ms 48852 KB Output is correct
8 Correct 42 ms 49996 KB Output is correct
9 Correct 107 ms 51284 KB Output is correct
10 Correct 23 ms 47200 KB Output is correct
11 Correct 28 ms 47260 KB Output is correct
12 Correct 30 ms 47364 KB Output is correct
13 Correct 28 ms 47372 KB Output is correct
14 Correct 33 ms 47316 KB Output is correct
15 Correct 34 ms 48120 KB Output is correct
16 Correct 44 ms 48964 KB Output is correct
17 Correct 45 ms 50004 KB Output is correct
18 Correct 103 ms 51336 KB Output is correct
19 Execution timed out 1591 ms 49080 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Execution timed out 1578 ms 49228 KB Time limit exceeded
3 Halted 0 ms 0 KB -