| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 955468 | 2024-03-30T13:58:19 Z | hariaakas646 | 007 (CEOI14_007) | C++14 | 199 ms | 16472 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[e]);
}
}
}
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 | 0 ms | 344 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 | 356 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 | 344 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 | 1 ms | 348 KB | Output is correct |
| 12 | Incorrect | 1 ms | 348 KB | Output isn't correct |
| 13 | Correct | 0 ms | 348 KB | Output is correct |
| 14 | Correct | 0 ms | 348 KB | Output is correct |
| 15 | Correct | 0 ms | 348 KB | Output is correct |
| 16 | Correct | 0 ms | 344 KB | Output is correct |
| 17 | Correct | 1 ms | 348 KB | Output is correct |
| 18 | Incorrect | 1 ms | 348 KB | Output isn't correct |
| 19 | Correct | 1 ms | 348 KB | Output is correct |
| 20 | Correct | 1 ms | 348 KB | Output is correct |
| 21 | Correct | 1 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 | 13 ms | 3164 KB | Output is correct |
| 2 | Correct | 19 ms | 4452 KB | Output is correct |
| 3 | Correct | 17 ms | 3184 KB | Output is correct |
| 4 | Incorrect | 20 ms | 4696 KB | Output isn't correct |
| 5 | Correct | 14 ms | 2908 KB | Output is correct |
| 6 | Correct | 14 ms | 3420 KB | Output is correct |
| 7 | Correct | 15 ms | 3676 KB | Output is correct |
| 8 | Correct | 16 ms | 3544 KB | Output is correct |
| 9 | Correct | 27 ms | 4132 KB | Output is correct |
| 10 | Correct | 140 ms | 8636 KB | Output is correct |
| 11 | Incorrect | 29 ms | 6488 KB | Output isn't correct |
| 12 | Correct | 40 ms | 7888 KB | Output is correct |
| 13 | Incorrect | 32 ms | 6748 KB | Output isn't correct |
| 14 | Correct | 26 ms | 5716 KB | Output is correct |
| 15 | Correct | 36 ms | 8028 KB | Output is correct |
| 16 | Correct | 39 ms | 8520 KB | Output is correct |
| 17 | Correct | 35 ms | 7508 KB | Output is correct |
| 18 | Correct | 35 ms | 7504 KB | Output is correct |
| 19 | Correct | 64 ms | 8788 KB | Output is correct |
| 20 | Correct | 138 ms | 11872 KB | Output is correct |
| 21 | Correct | 56 ms | 11540 KB | Output is correct |
| 22 | Correct | 45 ms | 9556 KB | Output is correct |
| 23 | Correct | 57 ms | 10900 KB | Output is correct |
| 24 | Partially correct | 51 ms | 11044 KB | Partially correct |
| 25 | Incorrect | 49 ms | 10260 KB | Output isn't correct |
| 26 | Correct | 46 ms | 9812 KB | Output is correct |
| 27 | Correct | 53 ms | 10876 KB | Output is correct |
| 28 | Correct | 67 ms | 11088 KB | Output is correct |
| 29 | Correct | 91 ms | 11212 KB | Output is correct |
| 30 | Correct | 156 ms | 12876 KB | Output is correct |
| 31 | Incorrect | 64 ms | 13396 KB | Output isn't correct |
| 32 | Correct | 73 ms | 11028 KB | Output is correct |
| 33 | Correct | 55 ms | 11348 KB | Output is correct |
| 34 | Incorrect | 65 ms | 11860 KB | Output isn't correct |
| 35 | Incorrect | 55 ms | 12116 KB | Output isn't correct |
| 36 | Incorrect | 56 ms | 12556 KB | Output isn't correct |
| 37 | Correct | 65 ms | 13216 KB | Output is correct |
| 38 | Correct | 74 ms | 12876 KB | Output is correct |
| 39 | Correct | 70 ms | 12908 KB | Output is correct |
| 40 | Correct | 120 ms | 14468 KB | Output is correct |
| 41 | Correct | 199 ms | 16472 KB | Output is correct |