Submission #29824

#TimeUsernameProblemLanguageResultExecution timeMemory
29824cdemirer007 (CEOI14_007)C++14
6 / 100
1000 ms26580 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> llp; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef vector<vii> vvii; #define mp(x, y) make_pair(x, y) #define pb(x) push_back(x) int N, M; int Z, D, SV1, SV2; vvi edges; int Ddists[200000], Zdists[200000]; int Dparents[200000]; void dijsktra(int *dists, int s) { set<ii> S; for (int i = 0; i < N; i++) { if (i == s) { dists[i] = 0; S.insert(mp(dists[i], i)); continue; } dists[i] = (int)1e9; S.insert(mp(dists[i], i)); } while ( ! S.empty() ) { ii x = *S.begin(); S.erase(S.begin()); for (int i = 0; i < edges[x.second].size(); i++) { if (dists[x.second] + 1 < dists[edges[x.second][i]]) { S.erase(mp(dists[edges[x.second][i]], edges[x.second][i])); dists[edges[x.second][i]] = dists[x.second] + 1; if (s == D) Dparents[edges[x.second][i]] = x.second; S.insert(mp(dists[edges[x.second][i]], edges[x.second][i])); } } } } int main(int argc, char **argv) { //freopen("input", "r", stdin); //freopen("output", "w", stdout); scanf("%d%d", &N, &M); scanf("%d%d%d%d", &Z, &D, &SV1, &SV2); Z--; D--; SV1--; SV2--; edges.resize(N); for (int i = 0; i < M; i++) { int a, b; scanf("%d%d", &a, &b); a--, b--; edges[a].pb(b); edges[b].pb(a); } Dparents[D] = -1; dijsktra(Ddists, D); dijsktra(Zdists, Z); int best1 = -1; int best2 = -1; int x = SV1; while (x != -1) { //if (x) cerr << x << endl; int fark = Ddists[x] - Zdists[x]; best1 = max(best1, fark); x = Dparents[x]; } x = SV2; while (x != -1) { int fark = Ddists[x] - Zdists[x]; best2 = max(best2, fark); x = Dparents[x]; } if (Dparents[SV1] == SV2) best2 = max(best2, Ddists[SV1] - Zdists[SV1] + 1); if (Dparents[SV2] == SV1) best1 = max(best1, Ddists[SV2] - Zdists[SV2] + 1); int ans = min(best1, best2); printf("%d\n", (ans!=-1?ans-1:-1)); return 0; }

Compilation message (stderr)

007.cpp: In function 'void dijsktra(int*, int)':
007.cpp:33:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges[x.second].size(); i++) {
                     ^
007.cpp: In function 'int main(int, char**)':
007.cpp:49:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
007.cpp:50:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &Z, &D, &SV1, &SV2);
                                       ^
007.cpp:54:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
                                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...