oj.uz

Submission #702550

# Submission time Handle Problem Language Result Execution time Memory
702550 2023-02-24T11:28:15 Z Chal1shkan Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 128056 KB 
# include <bits/stdc++.h>

# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x  << " = " << x << endl; 

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ll maxn = 1e5 + 25;
const ll inf = 2e9 + 0;
const ll mod = 998244353;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};

using namespace std;

int n, q;
pair <pair <int, int>, int> p[5003];
int dist[5003][5003];
vector <int> g[5003];

void dijkstra (int st)
{
	dist[st][st] = 0;
	set <pair <int, int> > q;
	q.insert({0, st});
	while (!q.empty())
	{
		int v = q.begin() -> ss;
		q.erase(q.begin());
		for (int to : g[v])
		{
			if (dist[st][to] > dist[st][v] + 1)
			{
				q.erase({dist[st][to], to});
				dist[st][to] = dist[st][v] + 1;
				q.insert({dist[st][to], to});
			}
		}
	}
}

bool cmp (pair <pair <int, int>, int> a, pair <pair <int, int>, int> b)
{
	if (a.ff.ss != b.ff.ss)
	{
		return a.ff.ss < b.ff.ss;
	}
	else
	{
		return a.ff.ff < b.ff.ff;
	}
}

void ma1n (/* SABR */)
{
	cin >> n >> q;
	for (int i = 1; i <= n; ++i)
	{
		cin >> p[i].ff.ff >> p[i].ff.ss;
		p[i].ss = i;
	}
	sort(p + 1, p + 1 + n, cmp);
	if (n <= 5000)
	{
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 1; j < i; ++j)
			{
				if (p[i].ff.ff <= p[j].ff.ss)
				{
					g[p[j].ss].pb(p[i].ss);
				}
			}
			for (int j = 1; j <= n; ++j)
			{
				dist[i][j] = inf;
			}
		}
		for (int i = 1; i <= n; ++i)
		{
			dijkstra(i);
		}
		while (q--)
		{
			int id1, id2;
			cin >> id1 >> id2;
			if (dist[id1][id2] == inf)
			{
				cout << "impossible" << nl;
			}
			else
			{
				cout << dist[id1][id2] << nl;
			}
		}
	}
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("angry.in", "r", stdin);
//    freopen("angry.out", "w", stdout);
    int ttt = 1;
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << ' ';
        ma1n();
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Runtime error 3 ms 980 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 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 25 ms 8440 KB Output is correct
4 Correct 14 ms 8456 KB Output is correct
5 Correct 26 ms 8404 KB Output is correct
6 Correct 112 ms 9268 KB Output is correct
7 Correct 280 ms 10068 KB Output is correct
8 Correct 309 ms 11100 KB Output is correct
9 Correct 303 ms 11096 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 25 ms 8440 KB Output is correct
4 Correct 14 ms 8456 KB Output is correct
5 Correct 26 ms 8404 KB Output is correct
6 Correct 112 ms 9268 KB Output is correct
7 Correct 280 ms 10068 KB Output is correct
8 Correct 309 ms 11100 KB Output is correct
9 Correct 303 ms 11096 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 24 ms 8456 KB Output is correct
13 Correct 16 ms 8464 KB Output is correct
14 Correct 27 ms 8444 KB Output is correct
15 Correct 107 ms 9252 KB Output is correct
16 Correct 274 ms 10120 KB Output is correct
17 Correct 344 ms 11104 KB Output is correct
18 Correct 308 ms 11100 KB Output is correct
19 Execution timed out 1585 ms 128056 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 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 25 ms 8440 KB Output is correct
4 Correct 14 ms 8456 KB Output is correct
5 Correct 26 ms 8404 KB Output is correct
6 Correct 112 ms 9268 KB Output is correct
7 Correct 280 ms 10068 KB Output is correct
8 Correct 309 ms 11100 KB Output is correct
9 Correct 303 ms 11096 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 30 ms 8432 KB Output is correct
13 Correct 22 ms 8404 KB Output is correct
14 Correct 28 ms 8404 KB Output is correct
15 Correct 109 ms 9252 KB Output is correct
16 Correct 266 ms 10100 KB Output is correct
17 Correct 322 ms 11084 KB Output is correct
18 Correct 297 ms 11052 KB Output is correct
19 Runtime error 3 ms 816 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 3 ms 724 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 1 ms 468 KB Output is correct
2 Runtime error 3 ms 980 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -