Submission #1288736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288736		ecen30	세계 지도 (IOI25_worldmap)	C++20	93 / 100	22 ms	4372 KiB

worldmap

//testing Ai code
// Strategy: Find a DFS tree and build a 3N grid with optimizations:
// - Don't return after reaching the deepest node
// - Only create an extra line for backedges if they go downward

#include "worldmap.h"
#include <vector>
#include <iostream>
#define debug 
using namespace std;

#define maxn 120
int longest[maxn];
int tin[maxn];
int vis[maxn];
int prof[maxn];

vector<int> add[maxn];

vector<vector<int> > G,T;
vector<vector<int> > ans;
int K;

int cnt;
int up;
int mxp;
int leaves;
int endpoint;

// DFS to build spanning tree and find longest path
pair<int,int> dfs(int vx,int par=-1){
  debug("dfs %d\n",vx);
	vis[vx] = 1;
	tin[vx] = cnt++;
	int depth = 0;
  pair<int,int> res ({0,vx});

	for(int viz : G[vx]){
		if(!vis[viz]){
			T[vx].push_back(viz);
			prof[viz] = 1 + prof[vx];
			auto u = dfs(viz,vx);
			if(u.first+1 > res.first){
				res.first = u.first+1;
				longest[vx] = viz;
        res.second = u.second;
			}
		}
		else if(tin[viz] > tin[vx]){
			// Backedge going down
			add[vx].push_back(viz);
		}
	}
	return res;
}

int N;

// Add tree edge to the grid
void add_edge(int a,int b){
  debug("add %d %d\n",a,b);
	if(K == 0){
		for(int i=0;i<3*N;i++)
			ans[0][i] = (i%2) ? a : b;
		K++;
		return;
	}
	if(ans[K-1][0] == b || ans[K-1][1] == b)
		swap(a,b);

	if(ans[K-1][0] == a)
		swap(a,b);

	for(int i=0;i<3*N;i++)
		ans[K][i] = (i%2) ? b : a;

	K++;
}

// Add backedges (non-tree edges)
void add_adj(int vx){
  if(K == 0){
    int t = 0;
    for(int i=0;i<3*N;i++){
      if(i%2 == 0 && t < add[vx].size()){
        ans[K][i] = add[vx][t];
        up = max(up, i+1);
        t++;
		  }
		  else
			  ans[K][i] = vx;
    }
    K++;
    return;
  }
	int t = 0;
	for(int i=0;i<3*N;i++){
		if(ans[K-1][i] == vx && t < add[vx].size()){
			ans[K][i] = add[vx][t];
      up = max(up, i+1);
			t++;
		}
		else
			ans[K][i] = vx;
	}
	K++;
}

int stop;

// Build the grid by traversing the tree
void dfs2(int vx,int ret){
  up = max(up,2);
  if(T[vx].size() == 0) {
    leaves++;
    if(vx == endpoint){
      debug("!stop\n");
      stop = 1;
    } 
    return;
  }
  debug("dfs2 %d longest %d list :",vx,longest[vx]); 
  for(int a : T[vx]) debug("%d ",a); 
  debug("\n");
  
	// Add backedges if any
	if(add[vx].size())
		add_adj(vx);

	// Process non-longest children first
	for(int viz : T[vx])
		if(viz != longest[vx]){
			add_edge(vx,viz);
			dfs2(viz,ret);
			if(!stop)
        add_edge(vx,viz);
		}

	// Process longest child (optimization: don't return from deepest path)
	add_edge(vx,longest[vx]);
  debug("oi");
	dfs2(longest[vx],0);
  if(!stop && T[longest[vx]].size() > 0)
    add_edge(vx,longest[vx]);
}

std::vector<std::vector<int> > create_map(int _N, int M, std::vector<int> A, std::vector<int> B) {
	// Initialization
  N = _N;
  if(N == 1){
    ans = vector<vector<int> > (1, vector<int>(1));
    ans[0][0] = 1;
    return ans;
  }
  
	G = vector<vector<int> > (N);
	T = vector<vector<int> > (N);
	ans = vector<vector<int> > (3*N, vector<int>(3*N));
	cnt = K = up = mxp = stop = leaves = 0;

	// Build adjacency list
	for (int i = 0; i < M; i++) {
		A[i]--;
		B[i]--;
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}

	for(int i=0;i<N;i++){
		vis[i] = 0;
    add[i].clear();
  }
  
  debug("ok\n");
  
	// Find spanning tree and longest path endpoint
	endpoint = dfs(0).second;
  debug("ok2\n");
  
	// Build the grid
	dfs2(0,1);
  debug("ok3\n");
  debug("diam %d, leaves %d\n",mxp,leaves);

	// Convert to 1-indexed
	for (int i = 0; i < int(ans.size()); i++) {
		for (int j = 0; j < int(ans.size()); j++) {
			ans[i][j]++;
		}
	}

  // Fill remaining rows
  for(int i=K;i<3*N;i++)
    for(int j=0;j<3*N;j++)
      ans[i][j] = ans[i-1][j];

  K = max(K,up);
  
  // Create final result with correct size
  vector<vector<int> > ret (K, vector<int>(K));
  for(int i=0;i<K;i++)
    for(int j=0;j<K;j++)
      ret[i][j] = ans[i][j];
      
	return ret;
}

• 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: 49 / 56