Submission #1263152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263152		nerrrmin	World Map (IOI25_worldmap)	C++20	72 / 100	73 ms	9540 KiB

worldmap

#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];
      |     ^~~~~

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 28 / 56