oj.uz

Submission #587611

# Submission time Handle Problem Language Result Execution time Memory
587611 2022-07-02T06:45:48 Z cfalas Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 42440 KB 
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;

#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)

int t, n;
vi a, b;
vector<vi> adj;
int ans[5500][5500];
int main(){
	int q;
	cin>>n>>q;
	adj.assign(n+1, vi());
	vii e(n);
	FOR(i,n){
		cin>>e[i].F>>e[i].S;
	}
	FOR(i,n){
		FOR(j,n){
			if(i==j) continue;
			if(e[j].F<=e[i].S && e[i].S<=e[j].S){
				adj[i+1].push_back(j+1);
			}
		}
		/*
		cout<<i+1<<": ";
		FOA(v, adj[i+1]) cout<<v<<" ";
		cout<<endl;
		*/
	}
	FORi(i,1,n+1){
		queue<ii> q;
		q.push({0, i});
		FOR(j,n+1) ans[i][j] = MOD;
		ans[i][i] = 0;
		while(!q.empty()){
			ii t = q.front();
			q.pop();

			if(-t.F > ans[i][t.S]) continue;

			FOA(v, adj[t.S]){
				if(ans[i][v] > 1 - t.F){
					ans[i][v] = 1 - t.F;
					q.push({-ans[i][v], v});
				}
			}

		}
	}
	while(q--){
		int a, b;
		cin>>a>>b;
		if(ans[a][b] < MOD) cout<<ans[a][b]<<endl;
		else cout<<"impossible\n";
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 1592 ms 4588 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 19 ms 8248 KB Output is correct
4 Correct 14 ms 8240 KB Output is correct
5 Correct 21 ms 8284 KB Output is correct
6 Correct 46 ms 9008 KB Output is correct
7 Correct 125 ms 9816 KB Output is correct
8 Correct 145 ms 10956 KB Output is correct
9 Correct 763 ms 12316 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 19 ms 8248 KB Output is correct
4 Correct 14 ms 8240 KB Output is correct
5 Correct 21 ms 8284 KB Output is correct
6 Correct 46 ms 9008 KB Output is correct
7 Correct 125 ms 9816 KB Output is correct
8 Correct 145 ms 10956 KB Output is correct
9 Correct 763 ms 12316 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 20 ms 8276 KB Output is correct
13 Correct 13 ms 8280 KB Output is correct
14 Correct 21 ms 8208 KB Output is correct
15 Correct 46 ms 9036 KB Output is correct
16 Correct 135 ms 9904 KB Output is correct
17 Correct 146 ms 10916 KB Output is correct
18 Correct 753 ms 12408 KB Output is correct
19 Execution timed out 1593 ms 42440 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 19 ms 8248 KB Output is correct
4 Correct 14 ms 8240 KB Output is correct
5 Correct 21 ms 8284 KB Output is correct
6 Correct 46 ms 9008 KB Output is correct
7 Correct 125 ms 9816 KB Output is correct
8 Correct 145 ms 10956 KB Output is correct
9 Correct 763 ms 12316 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 21 ms 8304 KB Output is correct
13 Correct 13 ms 8308 KB Output is correct
14 Correct 21 ms 8252 KB Output is correct
15 Correct 47 ms 9068 KB Output is correct
16 Correct 129 ms 9856 KB Output is correct
17 Correct 151 ms 10964 KB Output is correct
18 Correct 762 ms 12268 KB Output is correct
19 Execution timed out 1576 ms 4496 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 1588 ms 4592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 1592 ms 4588 KB Time limit exceeded
3 Halted 0 ms 0 KB -