| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 955469 | 2024-03-30T13:59:14 Z | hariaakas646 | 007 (CEOI14_007) | C++17 | 262 ms | 16416 KB |
#include <bits/stdc++.h>
using namespace std;
#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;
void usaco()
{
freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
// freopen("problem.out", "w", stdout);
}
int n, m;
vvi graph;
vi dist1, dist2;
vi bfs(int x) {
vi dist(n+1, 1e9);
vb vis(n+1);
queue<pii> q;
q.push(mp(x, 0));
while(q.size()) {
auto p = q.front();
q.pop();
if(vis[p.f]) continue;
// printf("%d\n", p.f);
vis[p.f] = true;
dist[p.f] = p.s;
for(auto e : graph[p.f]) {
// printf("%d ", e);
q.push(mp(e, p.s+1));
}
}
return dist;
}
vi dp;
int comp(int x) {
if(!dp[x]) {
for(auto e : graph[x]) {
if(dist1[e] < dist1[x] && dist1[e] == dist2[e]) {
dp[x] = max(comp(e)+1, dp[x]);
}
}
}
return dp[x];
}
int main() {
// usaco();
scd(n); scd(m);
int s1, s2, a, b;
scd(s1);
scd(s2);
scd(a);
scd(b);
graph = vvi(n+1);
frange(i, m) {
int a, b;
scd(a);
scd(b);
graph[a].pb(b);
graph[b].pb(a);
}
dist1 = bfs(a);
dist2 = bfs(b);
int w1 = dist1[s2] - dist1[s1];
int w2 = dist2[s2] - dist2[s1];
// printf("%d %d ", w1, w2);
// printf("%d %d %d %d\n", dist1[a], dist1[b], dist2[a], dist2[b]);
dp = vi(n+1);
if(w1 < 0 || w2 < 0) printf("-1");
else {
if(w1 != w2)
printf("%d", min(w1, w2));
else {
int c = comp(s1);
int d = comp(s2);
int w = w1;
// c + w is direction deciding time of 007.
// d is the direction deciding time of Mr Null.
if(c + w >= d) printf("%d", w);
else printf("%d", w-1);
}
}
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 348 KB | Output is correct |
| 2 | Correct | 0 ms | 348 KB | Output is correct |
| 3 | Correct | 0 ms | 348 KB | Output is correct |
| 4 | Correct | 0 ms | 348 KB | Output is correct |
| 5 | Correct | 0 ms | 348 KB | Output is correct |
| 6 | Correct | 0 ms | 348 KB | Output is correct |
| 7 | Correct | 0 ms | 348 KB | Output is correct |
| 8 | Correct | 0 ms | 348 KB | Output is correct |
| 9 | Correct | 1 ms | 348 KB | Output is correct |
| 10 | Correct | 0 ms | 348 KB | Output is correct |
| 11 | Correct | 0 ms | 348 KB | Output is correct |
| 12 | Correct | 0 ms | 348 KB | Output is correct |
| 13 | Correct | 1 ms | 344 KB | Output is correct |
| 14 | Correct | 1 ms | 348 KB | Output is correct |
| 15 | Correct | 0 ms | 348 KB | Output is correct |
| 16 | Correct | 1 ms | 348 KB | Output is correct |
| 17 | Correct | 0 ms | 348 KB | Output is correct |
| 18 | Correct | 0 ms | 348 KB | Output is correct |
| 19 | Correct | 1 ms | 348 KB | Output is correct |
| 20 | Correct | 1 ms | 356 KB | Output is correct |
| 21 | Correct | 0 ms | 348 KB | Output is correct |
| 22 | Correct | 1 ms | 348 KB | Output is correct |
| 23 | Correct | 1 ms | 348 KB | Output is correct |
| 24 | Correct | 1 ms | 348 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 15 ms | 3024 KB | Output is correct |
| 2 | Correct | 18 ms | 4444 KB | Output is correct |
| 3 | Correct | 15 ms | 3164 KB | Output is correct |
| 4 | Correct | 20 ms | 4700 KB | Output is correct |
| 5 | Correct | 13 ms | 2908 KB | Output is correct |
| 6 | Correct | 16 ms | 3280 KB | Output is correct |
| 7 | Correct | 21 ms | 3676 KB | Output is correct |
| 8 | Correct | 22 ms | 3632 KB | Output is correct |
| 9 | Correct | 26 ms | 4384 KB | Output is correct |
| 10 | Correct | 108 ms | 8648 KB | Output is correct |
| 11 | Correct | 29 ms | 6484 KB | Output is correct |
| 12 | Correct | 42 ms | 8020 KB | Output is correct |
| 13 | Correct | 43 ms | 6876 KB | Output is correct |
| 14 | Correct | 25 ms | 5712 KB | Output is correct |
| 15 | Correct | 36 ms | 8016 KB | Output is correct |
| 16 | Correct | 39 ms | 8536 KB | Output is correct |
| 17 | Correct | 39 ms | 7508 KB | Output is correct |
| 18 | Correct | 35 ms | 7508 KB | Output is correct |
| 19 | Correct | 65 ms | 8792 KB | Output is correct |
| 20 | Correct | 137 ms | 11916 KB | Output is correct |
| 21 | Correct | 54 ms | 11604 KB | Output is correct |
| 22 | Correct | 51 ms | 9496 KB | Output is correct |
| 23 | Correct | 51 ms | 10836 KB | Output is correct |
| 24 | Correct | 77 ms | 11088 KB | Output is correct |
| 25 | Correct | 60 ms | 10324 KB | Output is correct |
| 26 | Correct | 46 ms | 9812 KB | Output is correct |
| 27 | Correct | 53 ms | 11036 KB | Output is correct |
| 28 | Correct | 55 ms | 11096 KB | Output is correct |
| 29 | Correct | 88 ms | 11060 KB | Output is correct |
| 30 | Correct | 143 ms | 12764 KB | Output is correct |
| 31 | Correct | 63 ms | 13140 KB | Output is correct |
| 32 | Correct | 63 ms | 10888 KB | Output is correct |
| 33 | Correct | 78 ms | 11500 KB | Output is correct |
| 34 | Correct | 71 ms | 11792 KB | Output is correct |
| 35 | Correct | 58 ms | 11844 KB | Output is correct |
| 36 | Correct | 80 ms | 12232 KB | Output is correct |
| 37 | Correct | 77 ms | 13396 KB | Output is correct |
| 38 | Correct | 64 ms | 12900 KB | Output is correct |
| 39 | Correct | 69 ms | 13140 KB | Output is correct |
| 40 | Correct | 118 ms | 14420 KB | Output is correct |
| 41 | Correct | 262 ms | 16416 KB | Output is correct |