oj.uz

Submission #55951

# Submission time Handle Problem Language Result Execution time Memory
55951 2018-07-09T08:13:27 Z 노영훈(#1562) None (JOI16_dungeon2) C++11
44 / 100
 5 ms 984 KB 
#include "dungeon2.h"
#include <bits/stdc++.h>
using namespace std;

int n;

struct node {
    int adj[101];
    int deg, dep;
    int up_e, up_v;
    int color;
} V[101];

void my_move(int v, int e, int c){
    if(v>0) V[v].color=c;
    if(e<0) return;
    Move(e, c);
}

int init(int p=-1, int d=0){
    if(Color()!=1){
        my_move(-1, LastRoad(), Color());
        return 0;
    }
    int v=++n;
    node &nd=V[v];

    nd.deg=NumberOfRoads();
    nd.dep=d;
    nd.up_e=LastRoad();
    nd.up_v=p;

    for(int i=1; i<=nd.deg; i++){
        if(i==nd.up_e) { nd.adj[i]=-p; continue; }
        my_move(v, i, 2);
        nd.adj[i]=init(v, d+1);
    }

    my_move(v, nd.up_e, 3);
    return v;
}

int up;
void dfs1(int v=1){
    node &nd=V[v];
    for(int i=1; i<=nd.deg; i++){
        if(nd.adj[i]!=0) continue;
        my_move(v, i, 1);
        if(Color()==3){
            my_move(-1, LastRoad(), 3);
        }
        else{
            int thate=LastRoad();
            my_move(-1, thate, 1);
            int now=v;
            do{
                my_move(-1, V[now].up_e, Color());
                now=V[now].up_v;
            } while(Color()!=1);
            V[now].adj[thate]=-v;
            my_move(-1, thate, 2);
            V[v].adj[i]=-now;
        }
    }
    for(int i=1; i<=nd.deg; i++){
        if(nd.adj[i]<=0) continue;
        my_move(v, i, 2);
        dfs1(nd.adj[i]);
    }
    my_move(v, nd.up_e, 1);
}

void get_graph(){
    init();

    dfs1();

    // for(int i=1; i<=n; i++, cout<<'\n')
    //     for(int j=1; j<=V[i].deg; j++)
    //         cout<<V[i].adj[j]<<' ';

}

int cnt[101];
int dist[101];

void solve(){
    for(int i=1; i<=n; i++){
        queue<int> Q;
        for(int i=1; i<=n; i++) dist[i]=-1;
        dist[i]=0; Q.push(i);
        while(!Q.empty()){
            int v=Q.front(); Q.pop();
            for(int i=1; i<=V[v].deg; i++){
                int x=abs(V[v].adj[i]);
                if(dist[x]>=0) continue;
                dist[x]=dist[v]+1;
                Q.push(x);
            }
        }
        for(int i=1; i<=n; i++) cnt[dist[i]]++;
    }
}

void Inspect(int r){
    get_graph();
    solve();
    // for(int i=1; i<=n; i++) cout<<cnt[i]<<' ';
    // cout<<'\n';
    for(int i=1; i<=r; i++) Answer(i, cnt[i]/2);
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 3 ms 692 KB Output is correct
6 Correct 2 ms 692 KB Output is correct
7 Correct 2 ms 692 KB Output is correct
8 Correct 2 ms 692 KB Output is correct
9 Correct 2 ms 692 KB Output is correct
10 Correct 2 ms 692 KB Output is correct
11 Correct 2 ms 692 KB Output is correct
12 Correct 3 ms 708 KB Output is correct
13 Correct 2 ms 708 KB Output is correct
14 Correct 2 ms 708 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 708 KB Output is correct
2 Correct 5 ms 712 KB Output is correct
3 Correct 3 ms 712 KB Output is correct
4 Correct 3 ms 712 KB Output is correct
5 Correct 3 ms 712 KB Output is correct
6 Correct 3 ms 712 KB Output is correct
7 Correct 2 ms 712 KB Output is correct
8 Correct 2 ms 712 KB Output is correct
9 Correct 4 ms 712 KB Output is correct
10 Correct 4 ms 712 KB Output is correct
11 Correct 2 ms 712 KB Output is correct
12 Correct 2 ms 712 KB Output is correct
13 Correct 2 ms 712 KB Output is correct
14 Correct 3 ms 712 KB Output is correct
15 Correct 3 ms 712 KB Output is correct

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 984 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -