제출 #1262481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262481		user736482	Dungeon 2 (JOI16_dungeon2)	C++20	0 / 100	4 ms	840 KiB

dungeon2

#include<bits/stdc++.h>
#include "dungeon2.h"
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007 
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099

vector<ll>g[207],d[207],g2[207];
ll ak=1;
ll cur=0;
vector<vector<ll>>vec;
void dfs(ll v, ll par){
    //cout<<v<<" "<<par<<"  ";
    ll x=-1;
    if(v!=0)
    x=LastRoad()-1;
    if(Color()!=1){
        if(Color()==2)
        g[par].pb(0);
        else g[par].pb(-1);
        d[par].pb(-1);
        ak--;
        Move(x+1,2);
        return;
    }
    g[par].pb(-1);
    d[par].pb(v);
    ll y=NumberOfRoads();
    for(ll i=0;i<y;i++){
        if(i==x){g[v].pb(-1);d[v].pb(-1);}
        else{
            Move(i+1,2);
            dfs(ak++,v);
        }
    }
    if(v!=0)
    Move(x+1,3);
}

void dfs2(ll v, ll it){
    //cout<<v<<" ";
    ll x;
    if(v!=0)
    x=LastRoad()-1;  
    ll y=NumberOfRoads();
    for(ll i=0;i<y;i++){
        if(g[v][i]!=-1){
            Move(i+1,1);
            g[v][i]=g[v][i]*3+Color()-1;
            Move(LastRoad(),Color());
        }
    }
    for(ll i=0;i<y;i++){
        if(d[v][i]!=-1){
            Move(i+1,vec[v][it]);
            dfs2(d[v][i],it);
        }
    }
    if(v!=0)
    Move(x+1,Color());
}

void Inspect(int r){
    dfs(0,201);
    if(ak>50)cout<<"xd";
    //cout<<"xd";
    ll c=5;
    for(ll i=0;i<ak;i++){
        ll x=i;
        vec.pb({});
        for(ll j=0;j<c;j++){
            vec.back().pb(x%3+1);
            x/=3;
        }
        reverse(vec.back().begin(),vec.back().end());
    }
    /* for(ll i=0;i<ak;i++){
        cout<<i<<": ";
        for(ll j : d[i])cout<<j<<" ";
        cout<<"\n";
        for(ll j : g[i])cout<<j<<" ";
        cout<<"\n\n";
    }*/
    for(ll i=0;i<c;i++){
        dfs2(0,i);
        //cout<<"\n\n";
    }
   // cout<<ak<<" ";
    
   /* for(ll i=0;i<ak;i++){
        cout<<i<<": ";
        for(ll j : d[i])cout<<j<<" ";
        cout<<"\n";
        for(ll j : g[i])cout<<j<<" ";
        cout<<"\n\n"<<" ";
    }*/
    for(ll i=0;i<ak;i++){
        for(ll j : d[i]){
            if(j!=-1){
                g2[i].pb(j);
                g2[j].pb(i);
            }

        }
        for(ll j : g[i]){
            if(j!=-1){
                g2[i].pb(j);
                g2[j].pb(i);
            }
            
        }
    }
   /* for(ll i=0;i<ak;i++){
        cout<<i<<": ";
        for(ll j : g2[i])cout<<j<<" ";
        cout<<"\n\n";
    }*/
    ll ans[207];
    ll dst[207];

    for(ll i=0;i<207;i++){
        ans[i]=0;
    }
    priority_queue<pair<ll,ll>>pq;

    for(ll i=0;i<ak;i++){
        for(ll j=0;j<207;j++)dst[j]=-1;
        pq.push({0,i});
        while(pq.size()){
            auto pom=pq.top();
            pq.pop();
            if(dst[pom.ss]!=-1)continue;
            dst[pom.ss]=-pom.ff;
            for(ll j : g2[pom.ss])pq.push({pom.ff-1,j});
        }
        for(ll j=0;j<ak;j++)ans[dst[j]]++;
    }
    for(ll i=1;i<=r;i++){//cout<<i<<" "<<ans[i]<<"\n";
    Answer(i,ans[i]/2);}
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 27
• Subtask 3: 0 / 56