oj.uz

Submission #702549

# Submission time Handle Problem Language Result Execution time Memory
702549 2023-02-24T11:27:21 Z Chal1shkan Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 253092 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 = 1e18 + 0;
const ll mod = 998244353;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};

using namespace std;

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

void dijkstra (ll st)
{
	dist[st][st] = 0;
	set <pair <ll, ll> > q;
	q.insert({0, st});
	while (!q.empty())
	{
		ll v = q.begin() -> ss;
		q.erase(q.begin());
		for (ll 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 <ll, ll>, ll> a, pair <pair <ll, ll>, ll> 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 (ll 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 (ll i = 1; i <= n; ++i)
		{
			for (ll j = 1; j < i; ++j)
			{
				if (p[i].ff.ff <= p[j].ff.ss)
				{
					g[p[j].ss].pb(p[i].ss);
				}
			}
			for (ll j = 1; j <= n; ++j)
			{
				dist[i][j] = inf;
			}
		}
		for (ll i = 1; i <= n; ++i)
		{
			dijkstra(i);
		}
		while (q--)
		{
			ll 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 2 ms 2644 KB Output is correct
2 Incorrect 34 ms 7052 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 30 ms 14592 KB Output is correct
4 Correct 19 ms 14648 KB Output is correct
5 Correct 31 ms 14548 KB Output is correct
6 Correct 102 ms 16316 KB Output is correct
7 Correct 247 ms 17904 KB Output is correct
8 Correct 282 ms 19860 KB Output is correct
9 Correct 249 ms 19904 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 30 ms 14592 KB Output is correct
4 Correct 19 ms 14648 KB Output is correct
5 Correct 31 ms 14548 KB Output is correct
6 Correct 102 ms 16316 KB Output is correct
7 Correct 247 ms 17904 KB Output is correct
8 Correct 282 ms 19860 KB Output is correct
9 Correct 249 ms 19904 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 30 ms 14548 KB Output is correct
13 Correct 23 ms 14548 KB Output is correct
14 Correct 31 ms 14592 KB Output is correct
15 Correct 101 ms 16316 KB Output is correct
16 Correct 242 ms 17876 KB Output is correct
17 Correct 289 ms 19952 KB Output is correct
18 Correct 253 ms 19928 KB Output is correct
19 Execution timed out 1589 ms 253092 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 30 ms 14592 KB Output is correct
4 Correct 19 ms 14648 KB Output is correct
5 Correct 31 ms 14548 KB Output is correct
6 Correct 102 ms 16316 KB Output is correct
7 Correct 247 ms 17904 KB Output is correct
8 Correct 282 ms 19860 KB Output is correct
9 Correct 249 ms 19904 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 30 ms 14628 KB Output is correct
13 Correct 21 ms 14596 KB Output is correct
14 Correct 32 ms 14548 KB Output is correct
15 Correct 101 ms 16212 KB Output is correct
16 Correct 253 ms 17888 KB Output is correct
17 Correct 275 ms 19844 KB Output is correct
18 Correct 256 ms 19908 KB Output is correct
19 Incorrect 46 ms 6920 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 7136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 34 ms 7052 KB Output isn't correct
3 Halted 0 ms 0 KB -