Submission #1295048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295048		nozika	World Map (IOI25_worldmap)	C++20	15 / 100	13 ms	3244 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;

map<pair<int,int>,int> used;
vector<int> adj[41];
vector<int> path, seq;

int edge[41][41], vis[41];
int N_nodes, K;



void print_matrix(vector<vector<int>> X){
   
   
    int n = X.size();
    
    
    
    for (int i = 0; i < n; i++){
       
       
        for (int j = 0; j < n; j++) cout << X[i][j] << " ";
      
      
       
       
        cout << endl;
   
   
    }
    system("pause");
}

void dfs_tree(int parent, int node){
   
   
   
   
    int deg = adj[node].size(); 
   
   
    for (int i = 0; i < deg; i++){
    
    
    
        int nxt = adj[node][i];
    
    
        if (nxt != parent) {
    
    
            path.push_back(node);
    
    
            dfs_tree(node, nxt);
    
    
        }
    }
    
    
    if (node != 1) path.push_back(node);
}

void dfs_general(int parent, int node){ 
    vis[node] = 1;
    for (int i = 1; i <= N_nodes; i++)
        if (!vis[i] && edge[node][i] == 1) {
            path.push_back(node);
            dfs_general(node, i); 
        }
    if (node != 1) path.push_back(node);
}

vector<vector<int>> create_map(int N, int M, 
                               vector<int> A, vector<int> B) {

    N_nodes = N;

    if (M == 0) {
        vector<vector<int>> grid(1, vector<int>(1, 1));
     
     
     
        return grid;
    
      
      
    }

    if (M == N - 1) { 
      
        for (int i = 1; i <= N; i++) adj[i].clear();
     
     
     
        for (int i = 0; i < M; i++){
        
        
            adj[A[i]].push_back(B[i]);
       
       
       
            adj[B[i]].push_back(A[i]);
        }
        path.clear();
        dfs_tree(0, 1);

        K = path.size();
        vector<vector<int>> grid(K, vector<int>(K, 1));
        for (int i = 0; i < K; i++)
            for (int j = 0; j < K; j++)
                grid[i][j] = path[j];
        return grid; 
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) edge[i][j] = 0;
        vis[i] = 0;
    }
       
    for (int i = 0; i < M; i++){
        edge[A[i]][B[i]] = 1;
        edge[B[i]][A[i]] = 1;
    }

    path.clear();
    dfs_general(0, 1);  

    seq.clear();
    used.clear();
    for (int i = 1; i <= N_nodes; i++) vis[i] = 0;

    K = path.size();
   
   
    int cnt = 0;


   
   
    for (int i = 0; i < K; i++){  	
      
      
        seq.push_back(path[i]);
     
     
     
        if (vis[path[i]] == 0) {
       
       
       
            seq.push_back(-1);
       
       
            seq.push_back(path[i]);
      
      
            vis[path[i]] = 1;
       
       
       
            cnt++;
     
     
     
            if (cnt == N) break;	
    
    
        }
  
  
  
    }

  
  
  
    K = seq.size();
 
 
   vector<vector<int>> grid(K, vector<int>(K, -1));

  
  
    for (int i = 0; i < K; i++) 
    
    
    
        grid[0][i] = seq[i];
      
  
  
  
    for (int u = 1; u <= N_nodes; u++)
     
     
        for (int v = 1; v < u; v++) 
       
       
       
            if (edge[v][u]) {
            
            
            
                pair<int,int> p = make_pair(v,u);
             
             
             
                if (used[p] == 0){
                
                
                    int col = -1;
                 
                 
                    for (int i = 0; i < K; i++)
                        if (grid[0][i] == v) { col = i + 1; break; }
                 
                 
                    
                
                
                    for (int i = 0; i < K; i++)
                 
                 
                        if (grid[i][col] == -1) {
                  
                  
                  
                            grid[i][col] = u; 
                  
                  
                  
                            grid[i][col - 1] = v;
                 
                 
                            grid[i + 1][col] = v;  	      
                 
                 
                 
                            grid[i + 1][col - 1] = v;  	      
                 
                 
                            break;
                
                
                
                        }
               
               
               
                    used[p] = 1;
          
          
                }
            }
	
    
    
    
    for (int i = 0; i < K; i++)
      
      
      
        for (int j = 0; j < K; j++)    
        
        
            if (grid[i][j] == -1) {
        
        
        
                if (i == 0) grid[i][j] = grid[i][j - 1];
        
        
        
                else        grid[i][j] = grid[i - 1][j]; 
      
      
            }



   
   
    return grid;
}

Compilation message (stderr)

worldmap.cpp: In function 'void print_matrix(std::vector<std::vector<int> >)':
worldmap.cpp:33:11: warning: ignoring return value of 'int system(const char*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     system("pause");
      |     ~~~~~~^~~~~~~~~

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