Submission #730571

#	Time	Username	Problem	Language	Result	Execution time	Memory
730571		abcvuitunggio	Dungeon 2 (JOI16_dungeon2)	C++17	81 / 100	23 ms	2132 KiB

dungeon2

#include "dungeon2.h"
#include <bits/stdc++.h>
using namespace std;
int g[201][201],d[201][201],matrix[201][201],mat[201][201],p[201],par[201],id=1;
vector <pair <int, int>> ve;
vector <int> ke[201];
set <int> s[201];
queue <int> q;
void findnode(int u){
    if (s[u].empty()){
        if (u!=1)
            Move(p[u],3);
        return;
    }
    for (int i:s[u]){
        Move(i,1);
        Move(LastRoad(),1);
    }
    int cur=u,cnt=s[u].size(),cnt2=0,v=0,i;
    for (i=ve.size()-1;i>=0;i--){
        if (!cnt&&!cnt2)
            break;
        Move(p[cur],2+(cur==u));
        cur=par[cur];
        if (Color()==1){
            g[u][cur]=g[cur][u]=1;
            cnt--;
            if (!cnt&&!cnt2)
                break;
        }
        if (!cnt2&&!s[cur].empty()){
            v=cur;
            vector <int> ve;
            for (int i:s[v]){
                Move(i,Color());
                if (Color()==2)
                    ve.push_back(i);
                Move(LastRoad(),(Color()==2?3:1));
            }
            for (int i:ve)
                s[v].erase(i);
            cnt2=ve.size();
        }
        if (Color()==3){
            g[v][cur]=g[cur][v]=1;
            cnt2--;
            if (!cnt&&!cnt2)
                break;
        }
    }
    for (;i<ve.size()-1;i++)
        Move(ve[i].second,2);
}
void dfs(int u){
    p[u]=LastRoad();
    int cnt=NumberOfRoads();
    vector <int> V;
    for (int i=1;i<=cnt;i++)
        if (i!=p[u]){
            Move(i,2);
            if (Color()==3){
                Move(LastRoad(),3);
                continue;
            }
            if (Color()==1){
                ve.push_back({u,i});
                id++;
                g[u][id]=g[id][u]=1;
                par[id]=u;
                dfs(id);
                ve.pop_back();
                continue;
            }
            s[u].insert(i);
            Move(LastRoad(),2);
        }
    findnode(u);
}
void Inspect(int R){
    dfs(1);
    int n=id;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (g[i][j])
                ke[i].push_back(j);
    memset(d,-1,sizeof(d));
    int cnt=0;
    for (int i=1;i<=n;i++){
        cnt+=ke[i].size();
        q.push(i);
        d[i][i]=0;
        while (!q.empty()){
            int u=q.front();
            q.pop();
            for (int v:ke[u])
                if (d[i][v]==-1){
                    d[i][v]=d[i][u]+1;
                    q.push(v);
                }
        }
    }
	for (int i=1;i<=R;i++){
		int cnt=0;
        for (int j=1;j<=n;j++)
            for (int k=j+1;k<=n;k++)
                cnt+=(d[j][k]==i);
        Answer(i,cnt);
	}
}

Compilation message (stderr)

dungeon2.cpp: In function 'void findnode(int)':
dungeon2.cpp:51:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (;i<ve.size()-1;i++)
      |           ~^~~~~~~~~~~~

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