Submission #601781

#TimeUsernameProblemLanguageResultExecution timeMemory
601781JeanBombeurStranded Far From Home (BOI22_island)C++17
0 / 100
381 ms524288 KiB
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int MAX_VILLAGE = (2e5); vector <int> Adj[MAX_VILLAGE]; long long Size[MAX_VILLAGE]; pair <int, int> Sorted[MAX_VILLAGE]; bool Vu[MAX_VILLAGE]; long long Dsu[MAX_VILLAGE]; bool Valid[MAX_VILLAGE]; int nbVillages, nbRoads; int Find(int a) { if (Dsu[a] < 0) return a; int p = Find(Dsu[a]); Valid[a] &= Valid[Dsu[a]]; return Dsu[a] = p; } void Union(int old, int big) { old = Find(old); if (- Dsu[old] < Size[big]) Valid[old] = false; Dsu[big] = Dsu[old] - Size[big]; Dsu[old] = big; return; } void Read() { scanf("%d %d", &nbVillages, &nbRoads); for (int i = 0; i < nbVillages; i ++) { Valid[i] = true; scanf("%lld", &Size[i]); Sorted[i] = {Size[i], i}; Dsu[i] = - Size[i]; } sort(Sorted, Sorted + nbVillages); for (int i = 0; i < nbRoads; i ++) { int a, b; scanf("%d %d", &a, &b); Adj[-- a].push_back(-- b); Adj[b].push_back(a); } return; } void Solve() { for (int i = 0; i < nbVillages; i ++) { int cur = Sorted[i].second; Vu[cur] = true; for (int dest : Adj[cur]) { if (Vu[dest]) Union(dest, cur); } } for (int i = 0; i < nbVillages; i ++) { printf("%c", Valid[i] ? '1' : '0'); } printf("\n"); return; } int main() { Read(); Solve(); return 0; }

Compilation message (stderr)

island.cpp: In function 'void Read()':
island.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d %d", &nbVillages, &nbRoads);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
island.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%lld", &Size[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
island.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
#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...