제출 #1302703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1302703		aaaaaaaa	세계 지도 (IOI25_worldmap)	C++20	58 / 100	164 ms	19556 KiB

worldmap

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

#define all(x) x.begin(), x.end()

const int mxN = 42;

vector<int> adj[mxN], waiting[mxN];
vector<int> ord;
int parent[mxN], leaf[mxN];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};


int find(int u){
    if(parent[u] == u) return u;
    return parent[u] = find(parent[u]);
}

bool unite(int u, int v){
    u = find(u), v = find(v);
    if(u == v) return 0;
    parent[u] = v;
    return 1;
}

void dfs(int u = 1, int par = 0){

    for(auto it : adj[u]){
        if(it ^ par) {
             ord.push_back(u);
             dfs(it, u);
        }
    }
    if(u != 1) ord.push_back(u);
}

void reset(int N){
    ord.clear();
    for(int i = 1; i <= N; ++i){
        adj[i].clear();
        waiting[i].clear();
        parent[i] = i;
        leaf[i] = 0;
    }
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    reset(N);
    vector<vector<bool>> mat(N + 5, vector<bool> (N + 5, 0));
  if(N == 1){
    return {{1}};
  }
  for(int i = 0; i < M; ++i){
    if(unite(A[i], B[i])){
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    waiting[A[i]].push_back(B[i]);
    waiting[B[i]].push_back(A[i]);
    mat[A[i]][B[i]] = 1;
    mat[B[i]][A[i]] = 1;
    mat[A[i]][A[i]] = 1;
    mat[B[i]][B[i]] = 1;
  }
  dfs(1, 0);
  vector<vector<int>> ans;
  int mx = 0;

  for(int i = 0; i < ord.size(); ++i){
    if(leaf[ord[i]]) {
        leaf[ord[i]] = 0;
        continue;
    }
    vector<int> top_layer = {ord[i]};
    vector<int> mid_layer;

    for(auto it : waiting[ord[i]]){
        mid_layer.push_back(it);
        mid_layer.push_back(ord[i]);
    }

    mx = max(mx, (int) mid_layer.size());

    ans.push_back(top_layer);
    if(mid_layer.size()) ans.push_back(mid_layer);
    ans.push_back(top_layer);
  }


    while(mx > ans.size()) ans.push_back(ans.back());

  for(int i = 0; i < (int) ans.size(); ++i){
        int x = ans[i][0];
        if(ans[i].size() > 1) x = ans[i][1];
        while((int) ans.size() > (int) ans[i].size()) {
            ans[i].push_back(x);
        }
        assert(ans.size() == ans[i].size());
  }


  assert(ans.size() <= 240);

reset(N);

    for(int i = 0; i < (int) ans.size(); ++i){
        assert(ans.size() == ans[i].size());
        for(int j = 0; j < (int) ans[i].size(); ++j){
            for(int k = 0; k < 4; ++k){
                int ni = i + dx[k], nj = j + dy[k];
                if(min(ni, nj) >= 0 && max(ni, nj) < (int) ans.size()){
                    assert(ans[i][j] <= N && ans[i][j] >= 1);
                   assert(ans[ni][nj] <= N && ans[ni][nj] >= 1);
                    if(ans[i][j] != ans[ni][nj]) {
                        //assert();
                        //cout << i << " " << j << "\n";
                        if(!mat[ans[i][j]][ans[ni][nj]]) cout << i << " " << j << "\n";
                    }
                }
            }
        }
    }


  return ans;
}

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