oj.uz

Submission #730505

# Submission time Handle Problem Language Result Execution time Memory
730505 2023-04-26T04:16:03 Z abcvuitunggio None (JOI16_dungeon2) C++17
44 / 100
 35 ms 1396 KB 
#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,ch[201];
vector <pair <int, int>> ve;
vector <int> ke[201];
queue <int> q;
int findnode(int u, int i){
    int j=LastRoad();
    Move(j,1);
    memset(ch,0,sizeof(ch));
    int cur=u;
    for (int i=ve.size()-1;i>=0;i--){
        Move(p[cur],Color());
        cur=par[cur];
        if (Color()==1){
            Move(j,2);
            return cur;
        }
    }
}
void dfs(int u){
    p[u]=LastRoad();
    int cnt=NumberOfRoads();
    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;
            }
            int v=findnode(u,i);
            g[u][v]=g[v][u]=1;
        }
    if (u!=1)
        Move(p[u],3);
}
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);
            g[i][j]=(g[i][j]?1:1e9);
        }
    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);
                }
        }
    }
	int i;
	for (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

dungeon2.cpp: In function 'int findnode(int, int)':
dungeon2.cpp:21:1: warning: control reaches end of non-void function [-Wreturn-type]
   21 | }
      | ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 572 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 564 KB Output is correct
10 Correct 1 ms 568 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 0 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 0 ms 568 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 628 KB Output is correct
15 Correct 1 ms 564 KB Output is correct

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1048 KB Output is correct
2 Partially correct 6 ms 1052 KB Partially correct
3 Partially correct 7 ms 980 KB Partially correct
4 Incorrect 35 ms 1396 KB Output isn't correct
5 Halted 0 ms 0 KB -