Submission #1295245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295245		gurkot	World Map (IOI25_worldmap)	C++20	72 / 100	59 ms	8500 KiB

worldmap

#include "worldmap.h"
#include <vector>
#include <map>
#include <iostream>
#include <cstdlib>
using namespace std;
map <pair<int,int>,int> mp;
vector <int> gr[41];
vector <int> ans,s;

int way[41][41],fix[41];
int n,k;

void myprint(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 go5(int u,int v){ 
 fix[v]=1;
 for (int i=1;i<=n;i++)
  if (fix[i]==0 && way[v][i]==1) {
   ans.push_back(v);
   go5(v,i); 
  }
  if (v!=1) ans.push_back(v);
}

vector<vector<int>> create_map(int N, int M, 
                    vector<int> A, vector<int> B) {
 n=N;
 if (M==0) {
  	vector <vector<int>> mymap(1, std::vector<int>(1, 1));
  	return mymap;
  } else {
 // **************** 5 ********************
  
  for (int i=1;i<=N;i++) {
   for (int j=1;j<=N;j++) way[i][j]=0;
   fix[i]=0;
  }
   
  for (int i=0;i<M;i++){
  	way[A[i]][B[i]]=1;
  	way[B[i]][A[i]]=1;
  }
  ans.clear();
  go5(0,1);  
 
  s.clear(); mp.clear();
  for (int i=1;i<=n;i++) fix[i]=0;
  k=ans.size();
  int cnt=0;
  for (int i=0;i<k;i++){  	
  	s.push_back(ans[i]);
  	if (fix[ans[i]]==0) {
  	  s.push_back(-1);
	  s.push_back(ans[i]);
	  fix[ans[i]]=1;
	  cnt++;
	  if (cnt==N) break;	
	}
  }
  k=s.size();
  vector<vector<int>> mymap(k, std::vector<int>(k, -1));
  for (int i=0;i<k;i++) mymap[0][i]=s[i];
  
  //cout<<"Mymap start:"<<endl;
  //myprint(mymap);
  
  for (int u=1;u<=n;u++)
   for (int v=1;v<u;v++) 
    if (way[v][u]) {
      pair <int,int> tmp=make_pair(v,u);
      if (mp[tmp]==0){  //  add(v,u);        
       int nom;
       for (int i=0;i<k;i++)
        if (s[i]==v) {nom=i+1; break;}
        
       for (int i=0;i<k;i++)
        if (mymap[i][nom]==-1) {
          mymap[i][nom]=u; mymap[i][nom-1]=v;
  	      mymap[i+1][nom]=mymap[i+1][nom-1]=v;  	      
  	      break;
        }        
	   mp[tmp]=1;
	   //cout<<"add: "<<v<<"-"<<u<<endl;
	   //myprint(mymap);
      }
	}//u,v
	
  for (int i=0;i<k;i++)
   for (int j=0;j<k;j++)    
    if (mymap[i][j]==-1) {
     if (i==0) mymap[i][j]=mymap[i][j-1];
          else mymap[i][j]=mymap[i-1][j]; 
   }
   return mymap;
 }//5
 
}

Compilation message (stderr)

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

• 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