제출 #881967

#제출 시각아이디문제언어결과실행 시간메모리
881967tsetEvacuation plan (IZhO18_plan)C++17
100 / 100
690 ms121476 KiB
#include<bits/stdc++.h> using namespace std; #define int long long const int INF = LLONG_MAX/6; vector<int> parentUF; vector<vector<int>> voisinDeArbre; vector<int> pereDe; vector<vector<int>> filsDe; vector<int > profNde; int getLeader(int nde) { if(parentUF[nde] == nde) return nde; parentUF[nde] = getLeader(parentUF[nde]); return parentUF[nde]; } void mergeUF(int u, int v) { int leaderU = getLeader(u); int leaderV = getLeader(v); if(leaderU != leaderV) parentUF[leaderU] = leaderV; } void dfsRoot(int nde, int ancestor, int prof) { pereDe[nde] = ancestor; profNde[nde] = prof; for(int iV : voisinDeArbre[nde]) { if(iV != ancestor) { filsDe[nde].push_back(iV); dfsRoot(iV, nde, prof+1); } } } signed main() { int nbNdes, nbArcs; scanf("%lld%lld", &nbNdes, &nbArcs); vector<vector<pair<int, int>>> voisinDe(nbNdes); vector<pair<int, int>> arcs; vector<tuple<int, int, int>> arcsSorted; for(int iA = 0; iA< nbArcs; iA++) { int u, v, pond; scanf("%lld%lld%lld", &u, &v, &pond); u--;v--; voisinDe[u].push_back({pond, v}); voisinDe[v].push_back({pond, u}); arcs.push_back({u, v}); } int nbSpe; scanf("%lld", &nbSpe); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for(int iSpe = 0; iSpe < nbSpe; iSpe++) { int u; scanf("%lld", &u); u--; pq.push({0, u}); } vector<int> pondNde(nbNdes, INF); while (!pq.empty()) { pair<int, int> pqTop = pq.top(); pq.pop(); int pondAct = pqTop.first; int ndeAct = pqTop.second; if(pondNde[ndeAct] == INF) { pondNde[ndeAct] = pondAct; for(pair<int, int> iV : voisinDe[ndeAct]) { pq.push({pondAct + iV.first, iV.second}); } } } for(int iArc = 0; iArc< nbArcs; iArc++) { int u = arcs[iArc].first, v = arcs[iArc].second; int pondArc = min(pondNde[u], pondNde[v]); arcsSorted.push_back({-pondArc, u, v}); } sort(arcsSorted.begin(), arcsSorted.end()); parentUF.resize(nbNdes); for(int iNde = 0; iNde< nbNdes; iNde++) { parentUF[iNde] = iNde; } voisinDeArbre.resize(nbNdes); for(tuple<int, int, int> arcAct: arcsSorted) { int u = get<1>(arcAct); int v = get<2>(arcAct); if(getLeader(u) != getLeader(v)) { mergeUF(u, v); voisinDeArbre[u].push_back(v); voisinDeArbre[v].push_back(u); } } pereDe.resize(nbNdes); filsDe.resize(nbNdes); profNde.resize(nbNdes); int root = 0; dfsRoot(root, root, 0); vector<vector<int>> goUpValue(nbNdes, vector<int>(20)); vector<vector<int>> goUpCrtq(nbNdes, vector<int>(20)); for(int iNde = 0; iNde< nbNdes; iNde++) { goUpValue[iNde][0] = pereDe[iNde]; goUpCrtq[iNde][0] = min(pondNde[iNde], pondNde[pereDe[iNde]]); } for(int powerTwo = 1; powerTwo< 20; powerTwo++) { for(int iNde = 0; iNde < nbNdes; iNde++) { goUpValue[iNde][powerTwo] = goUpValue[goUpValue[iNde][powerTwo-1]][powerTwo-1]; goUpCrtq[iNde][powerTwo] = min(goUpCrtq[iNde][powerTwo-1], goUpCrtq[goUpValue[iNde][powerTwo-1]][powerTwo-1]); } } int nbQueries; scanf("%lld", &nbQueries); for(int iQ =0; iQ< nbQueries; iQ++) { int u, v; scanf("%lld%lld", &u, &v); u--; v--; int minCtrqWh = min(pondNde[u], pondNde[v]); if(profNde[u]>profNde[v]) { int tmp = u; u = v; v = tmp; } for(int powerTwo = 19; powerTwo>=0; powerTwo--) { if(profNde[v] - (1 << powerTwo) >= profNde[u]) { minCtrqWh = min(minCtrqWh, goUpCrtq[v][powerTwo]); v = goUpValue[v][powerTwo]; } } for(int powerTwo = 19; powerTwo>=0; powerTwo--) { if(goUpValue[u][powerTwo] != goUpValue[v][powerTwo]) { minCtrqWh = min(minCtrqWh, goUpCrtq[u][powerTwo]); u = goUpValue[u][powerTwo]; minCtrqWh = min(minCtrqWh, goUpCrtq[v][powerTwo]); v = goUpValue[v][powerTwo]; } } if(u != v) { minCtrqWh = min(minCtrqWh, goUpCrtq[u][0]); } printf("%lld\n", minCtrqWh); } }

컴파일 시 표준 에러 (stderr) 메시지

plan.cpp: In function 'int main()':
plan.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%lld%lld", &nbNdes, &nbArcs);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%lld%lld%lld", &u, &v, &pond);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%lld", &nbSpe);
      |     ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%lld", &u);
      |         ~~~~~^~~~~~~~~~~~
plan.cpp:136:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |     scanf("%lld", &nbQueries);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
plan.cpp:141:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         scanf("%lld%lld", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...