oj.uz

Submission #595490

# Submission time Handle Problem Language Result Execution time Memory
595490 2022-07-13T19:04:04 Z Hacv16 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 209872 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(){
	cin >> n >> q;
	
	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]) 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 28 ms 47188 KB Output is correct
2 Runtime error 292 ms 209860 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Correct 26 ms 47260 KB Output is correct
3 Correct 31 ms 47352 KB Output is correct
4 Correct 33 ms 47348 KB Output is correct
5 Correct 30 ms 47304 KB Output is correct
6 Correct 36 ms 48016 KB Output is correct
7 Correct 51 ms 48936 KB Output is correct
8 Correct 48 ms 49996 KB Output is correct
9 Correct 105 ms 51344 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Correct 26 ms 47260 KB Output is correct
3 Correct 31 ms 47352 KB Output is correct
4 Correct 33 ms 47348 KB Output is correct
5 Correct 30 ms 47304 KB Output is correct
6 Correct 36 ms 48016 KB Output is correct
7 Correct 51 ms 48936 KB Output is correct
8 Correct 48 ms 49996 KB Output is correct
9 Correct 105 ms 51344 KB Output is correct
10 Correct 25 ms 47180 KB Output is correct
11 Correct 23 ms 47240 KB Output is correct
12 Correct 31 ms 47320 KB Output is correct
13 Correct 29 ms 47336 KB Output is correct
14 Correct 31 ms 47232 KB Output is correct
15 Correct 37 ms 48124 KB Output is correct
16 Correct 53 ms 48924 KB Output is correct
17 Correct 46 ms 49992 KB Output is correct
18 Correct 113 ms 51336 KB Output is correct
19 Execution timed out 1579 ms 47364 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Correct 26 ms 47260 KB Output is correct
3 Correct 31 ms 47352 KB Output is correct
4 Correct 33 ms 47348 KB Output is correct
5 Correct 30 ms 47304 KB Output is correct
6 Correct 36 ms 48016 KB Output is correct
7 Correct 51 ms 48936 KB Output is correct
8 Correct 48 ms 49996 KB Output is correct
9 Correct 105 ms 51344 KB Output is correct
10 Correct 29 ms 47188 KB Output is correct
11 Correct 28 ms 47244 KB Output is correct
12 Correct 32 ms 47312 KB Output is correct
13 Correct 29 ms 47268 KB Output is correct
14 Correct 30 ms 47348 KB Output is correct
15 Correct 33 ms 48084 KB Output is correct
16 Correct 48 ms 49036 KB Output is correct
17 Correct 42 ms 49996 KB Output is correct
18 Correct 108 ms 51328 KB Output is correct
19 Runtime error 282 ms 208600 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 278 ms 209872 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47188 KB Output is correct
2 Runtime error 292 ms 209860 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -