Submission #1259535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259535		alexdd	World Map (IOI25_worldmap)	C++20	12 / 100	1095 ms	8232 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
int n,K;
int dx[4] = {-1,+1,0,0};
int dy[4] = {0,0,-1,+1};
const int R = 6;
bool con[45][45],needs[45][45];
vector<vector<int>> mat,visited;
vector<int> getord()
{
    vector<pair<int,int>> v;
    for(int i=1;i<=n;i++)
    {
        int cnt = 0;
        for(int j=1;j<=n;j++)
            if(needs[i][j])
                cnt++;
        v.push_back({-cnt,i});
    }
    sort(v.begin(),v.end());
    vector<int> ord;
    for(auto [_,x]:v)
        ord.push_back(x);
    return ord;
}
bool fill(int x, int y)
{
    assert(mat[x][y] == 0);
    vector<int> ord = getord();
    int mxm=-1,care=-1;
    for(int val:ord)
    {
        bool bun = 1;
        int cate = 0;
        for(int v=0;v<4;v++)
        {
            int newx = x + dx[v], newy = y + dy[v];
            if(newx < 0 || newx >= K || newy < 0 || newy >= K)
                continue;
            if(mat[newx][newy] == 0)
                continue;
            if(!con[mat[newx][newy]][val])
            {
                bun = 0;
                break;
            }
            if(needs[mat[newx][newy]][val])
                cate++;
        }
        if(bun && cate > mxm)
        {
            mxm = cate;
            care = val;
        }
    }
    if(care == -1)
        return 0;
    mat[x][y] = care;
    for(int v=0;v<4;v++)
    {
        int newx = x + dx[v], newy = y + dy[v];
        if(newx < 0 || newx >= K || newy < 0 || newy >= K)
            continue;
        if(mat[newx][newy] == 0)
            continue;
        if(needs[mat[newx][newy]][care])
        {
            needs[mat[newx][newy]][care] = needs[care][mat[newx][newy]] = 0;
        }
    }
    return 1;
}
bool tot;
void dfs(int x, int y)
{
    visited[x][y] = 1;
    tot &= fill(x,y);
    for(int v=0;v<4;v++)
    {
        int newx = x + dx[v], newy = y + dy[v];
        if(newx < 0 || newx >= K || newy < 0 || newy >= K)
            continue;
        if(!visited[newx][newy] && mat[newx][newy] == 0)
            dfs(newx,newy);
    }
}
vector<vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B)
{
    n = N;
    K = N * R;
    mat.clear();
    mat.resize(K, vector<int>(K,0));
    visited = mat;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            con[i][j] = needs[i][j] = 0;
    for(int i=1;i<=N;i++)
        con[i][i] = 1;
    for(int i=0;i<M;i++)
    {
        needs[A[i]][B[i]] = needs[B[i]][A[i]] = 1;
        con[A[i]][B[i]] = con[B[i]][A[i]] = 1;
    }
    tot = 1;
    dfs(0,0);///K/2, K/2
    return mat;
}
/*

1
3 2
1 2
2 3

*/

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