Submission #1296217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296217		lizi14	World Map (IOI25_worldmap)	C++20	0 / 100	1 ms	572 KiB

worldmap

#include "worldmap.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
vector<int>j;
map<pair<int,int>,int>mp;
//const int N1=50;
vector<int>v[50];
//#include "worldmap.h"
int x[100];
int yuuu;
int bati[100][100];
void dfs(int a,int parent){
    x[parent]=1;
    for(int i=0; i<=yuuu; i++){
        if(x[i]==0 && bati[parent][i]==1){
            //j.push_back(a);
            j.push_back(parent);
            dfs(parent,i);
        }
    }
    if(parent!=1){
        j.push_back(parent);
    }
}
vector<vector<int>>create_map(int N, int M,vector<int> A,vector<int> B) {
    for(int i=0; i<50; i++){
        v[i].clear();
    }
    yuuu=N;
    j.clear();
    int n=A.size();
    for(int i=0; i<=N; i++){
        for(int j=0; j<=N; j++){
            bati[i][j]=0;
        }
    }
    for(int i=0; i<=N; i++){
        for(int j=0; j<=N; j++){
            bati[i][j]=0;
        }
    }
    for(int i=0; i<n; i++){
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
        bati[A[i]][B[i]]=1;
        bati[B[i]][A[i]]=1;
    }
    for(int i=0; i<=100; i++){
        x[i]=0;
    }
    dfs(0,1);
    // int batiii=j.size();
    // vector<vector<int>> ans(batiii, vector<int>(batiii));
    // for(int i=0; i<j.size(); i++){
    //     for(int drnachvi=0; drnachvi<j.size(); drnachvi++){
    //         ans[drnachvi][i]=j[i];
    //         //cout<<ans[drnachvi][i]<<" ";
    //     }
    //     //cout<<endl;
    // }
    // for(auto f:j){
    //     cout<<f<<" ";
    // }
    vector<int>drnachvi;
    drnachvi.clear();
    mp.clear();
    int ku=j.size();
    for(int i=0; i<ku; i++){
        drnachvi.push_back(j[i]);
        if(x[j[i]]==0){
            drnachvi.push_back(-19);
            drnachvi.push_back(j[i]);
            x[j[i]]=1;
        }
    }
    int batiii=drnachvi.size();
    vector<vector<int>> ans(batiii, vector<int>(batiii));
    for(int i=0; i<batiii; i++){
        ans[0][i]=drnachvi[i];
    }
    for(int i=1; i<=N; i++){
        for(int j=1; j<i; j++){
            if(bati[i][j]==1){
                pair<int,int>p={i,j};
                if(mp[p]==0){
                    int maomao=-1;
                    for(int i=0; i<batiii; i++){
                        if(drnachvi[i]==j){
                            maomao=i;
                            break;
                        }
                    }
                    if(maomao!=-1)maomao++;
                    for(int ka=0; ka<batiii; ka++){
                        if(ans[ka][maomao]==-19){
                            ans[ka][maomao]=i;
                            ans[ka][maomao-1]=j;
                            ans[ka+1][maomao]=j;
                            ans[ka+1][maomao-1]=j;
                            break;
                        }
                    }
                    mp[p]=1;
                }
            }
        }
    }
    for(int i=0; i<batiii; i++){
        for(int j=0; j<batiii; j++){
            if(ans[i][j]==-19){
                if(i==0){
                    ans[i][j]=ans[i][j-1];
                    continue;
                }
                ans[i][j]=ans[i-1][j];
            }
        }
    }
    
    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:51:13: warning: iteration 100 invokes undefined behavior [-Waggressive-loop-optimizations]
   51 |         x[i]=0;
      |         ~~~~^~
worldmap.cpp:50:19: note: within this loop
   50 |     for(int i=0; i<=100; i++){
      |                  ~^~~~~
worldmap.cpp:51:13: warning: 'void* __builtin_memset(void*, int, long unsigned int)' writing 404 bytes into a region of size 400 overflows the destination [-Wstringop-overflow=]
   51 |         x[i]=0;
      |         ~~~~^~
worldmap.cpp:11:5: note: destination object 'x' of size 400
   11 | int x[100];
      |     ^

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