Submission #29997

#TimeUsernameProblemLanguageResultExecution timeMemory
29997cdemirer007 (CEOI14_007)C++14
33.33 / 100
1000 ms27752 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], Zparents[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; else Zparents[edges[x.second][i]] = x.second; S.insert(mp(dists[edges[x.second][i]], edges[x.second][i])); } } } } bool flag[200000] = {0}; bool flag2[200000] = {0}; 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); Zparents[Z] = -1; dijsktra(Zdists, Z); int best1 = -1; int best2 = -1; int x = Dparents[SV1]; flag[SV1] = flag[SV2] = true; while (x != -1) { //if (x) cerr << x << endl; int fark = Ddists[x] - Zdists[x]; best1 = max(best1, fark); x = Dparents[x]; flag[x] = true; } x = Dparents[SV2]; int cntD = 1; while (x != -1) { if (flag[x] != true) cntD++; int fark = Ddists[x] - Zdists[x]; best2 = max(best2, fark); x = Dparents[x]; } x = Zparents[SV1]; int cntZ = 1; while (x != -1) { flag2[x] = true; x = Zparents[x]; } x = Zparents[SV2]; while (x != -1) { if (flag2[x] != true) cntZ++; x = Zparents[x]; } int sv1 = Ddists[SV1] - Zdists[SV1]; int sv2 = Ddists[SV2] - Zdists[SV2]; int minsv = min(sv1, sv2); int ans = -1; ans = max(ans, min(best1, best2)); ans = max(ans, minsv); //if (Dparents[SV1] == SV2) best1 = max(best1, Ddists[SV1] - Zdists[SV1] - 2); //if (Dparents[SV2] == SV1) best2 = max(best2, Ddists[SV2] - Zdists[SV2] - 2); //int ans = min(best1, best2); //if (Dparents[SV1] != SV2 && Dparents[SV2] != SV1 && min(best1, best2) != ans) ans = (ans!=-1?ans-1:-1); if (/*ans != min(best1, best2) && */Dparents[SV1] != SV2 && Dparents[SV2] != SV1 && Zparents[SV1] != SV2 && Zparents[SV2] != SV1 && cntD < cntZ) ans--; printf("%d\n", (ans!=-1?ans:-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:53: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:54: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:58: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...