oj.uz

Submission #587615

# Submission time Handle Problem Language Result Execution time Memory
587615 2022-07-02T06:50:24 Z cfalas Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 52924 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 vis[5500][5500];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	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, vis[i][j] = 0;
		ans[i][i] = 0;
		while(!q.empty()){
			ii t = q.front();
			q.pop();

			if(vis[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});
				}
			}
			vis[i][t.S] = true;

		}
	}
	while(q--){
		int a, b;
		cin>>a>>b;
		if(ans[a][b] < MOD) cout<<ans[a][b]<<"\n";
		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 1585 ms 4504 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 23 ms 16280 KB Output is correct
4 Correct 15 ms 16252 KB Output is correct
5 Correct 25 ms 16204 KB Output is correct
6 Correct 50 ms 17060 KB Output is correct
7 Correct 138 ms 17872 KB Output is correct
8 Correct 162 ms 18832 KB Output is correct
9 Correct 784 ms 20216 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 23 ms 16280 KB Output is correct
4 Correct 15 ms 16252 KB Output is correct
5 Correct 25 ms 16204 KB Output is correct
6 Correct 50 ms 17060 KB Output is correct
7 Correct 138 ms 17872 KB Output is correct
8 Correct 162 ms 18832 KB Output is correct
9 Correct 784 ms 20216 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 23 ms 16204 KB Output is correct
13 Correct 16 ms 16248 KB Output is correct
14 Correct 24 ms 16272 KB Output is correct
15 Correct 51 ms 16956 KB Output is correct
16 Correct 130 ms 17816 KB Output is correct
17 Correct 176 ms 18868 KB Output is correct
18 Correct 780 ms 20232 KB Output is correct
19 Execution timed out 1600 ms 52924 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 23 ms 16280 KB Output is correct
4 Correct 15 ms 16252 KB Output is correct
5 Correct 25 ms 16204 KB Output is correct
6 Correct 50 ms 17060 KB Output is correct
7 Correct 138 ms 17872 KB Output is correct
8 Correct 162 ms 18832 KB Output is correct
9 Correct 784 ms 20216 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 25 ms 16224 KB Output is correct
13 Correct 16 ms 16280 KB Output is correct
14 Correct 25 ms 16212 KB Output is correct
15 Correct 60 ms 17040 KB Output is correct
16 Correct 142 ms 17884 KB Output is correct
17 Correct 156 ms 18932 KB Output is correct
18 Correct 772 ms 20292 KB Output is correct
19 Execution timed out 1596 ms 4360 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 1592 ms 4432 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 1585 ms 4504 KB Time limit exceeded
3 Halted 0 ms 0 KB -