Submission #1263152

#TimeUsernameProblemLanguageResultExecution timeMemory
1263152nerrrminWorld Map (IOI25_worldmap)C++20
72 / 100
73 ms9540 KiB
#include "worldmap.h" #define pb push_back #include <bits/stdc++.h> using namespace std; const int maxn = 600; int n, m; vector < pair < int, int > > g[maxn]; vector < int > path; int used[maxn]; int seen[maxn]; void dfs(int beg, int from) { path.pb(beg); used[beg] = 1; for(auto &[nb, i]: g[beg]) { if(used[nb]) { continue; } if(nb == from) { continue; } dfs(nb, beg); path.pb(beg); } } int butai[maxn]; std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) { assert(M >= N-1); n = N; m = M; path.clear(); for (int i = 1; i <= n; ++ i) used[i] = 0; for (int i = 0; i <= 2*n; ++ i) g[i].clear(); for (int i = 0; i < m; ++ i) { g[A[i]].pb({B[i], i}); g[B[i]].pb({A[i], i}); } dfs(1, 0); int szp = path.size(); for (int i = 0; i <= n; ++ i) seen[i] = 0; for (int i = 0; i <= 600; ++ i) butai[i] = 0; vector < int > pat; for (int j = 0; j < szp; ++ j) { int ver = path[j]; pat.pb(ver); if(!seen[ver]) { pat.pb(ver); butai[pat.size()-1] = ver; pat.pb(ver); seen[ver] = 1; } } int szpat = pat.size(); std::vector<std::vector<int>> ans(szpat, std::vector<int>(szpat, 0)); for (int i = 0; i < szpat; ++ i) ans[0][i] = pat[i]; for (int j = 0; j < szpat; ++ j) { if(!butai[j]) { for(int i = 1; i < szpat; ++ i) ans[i][j] = ans[i-1][j]; } else { int i = 1; int v = butai[j]; for (auto &[x, iiii]: g[v]) { ans[i][j] = x; i ++; ans[i][j] = v; i ++; } while(i < szpat) { ans[i][j] = v; i ++; } } } return ans; }

Compilation message (stderr)

worldmap.cpp: In function 'std::vector<std::vector<int> > create_map(int, int, std::vector<int>, std::vector<int>)':
worldmap.cpp:53:18: warning: iteration 600 invokes undefined behavior [-Waggressive-loop-optimizations]
   53 |         butai[i] = 0;
      |         ~~~~~~~~~^~~
worldmap.cpp:52:23: note: within this loop
   52 |     for (int i = 0; i <= 600; ++ i)
      |                     ~~^~~~~~
worldmap.cpp:53:18: warning: 'void* __builtin_memset(void*, int, long unsigned int)' writing 2404 bytes into a region of size 2400 overflows the destination [-Wstringop-overflow=]
   53 |         butai[i] = 0;
      |         ~~~~~~~~~^~~
worldmap.cpp:31:5: note: destination object 'butai' of size 2400
   31 | int butai[maxn];
      |     ^~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...