oj.uz

답안 #513706

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
513706 2022-01-17T12:36:43 Z 79brue Snowy Roads (JOI16_snowy) C++14
0 / 100
 13 ms 1716 KB 
#include "Anyalib.h"
#include <bits/stdc++.h>

using namespace std;

static int n;
static vector<int> link[502];
static bool mark[502];
static int depth[502];
static int numLoc[502], locCnt;
static int low[502];

static int dfs(int x, int par = -1){
    int maxDepth = 0;
    for(auto y: link[x]){
        if(y == par) continue;
        depth[y] = depth[x] + 1;
        maxDepth = max(dfs(y, x)+1, maxDepth);
    }
    if(maxDepth == 12 || x==0){
        mark[x] = 1;
        numLoc[x] = locCnt;
        locCnt += 9;
        maxDepth = 0;
    }
    return maxDepth;
}

void InitAnya(int N, int A[], int B[]){
    n = N;
    for(int i=0; i<N-1; i++) link[A[i]].push_back(B[i]), link[B[i]].push_back(A[i]);
    locCnt = n;
    dfs(0);
    for(int i=0; i<N-1; i++){
        if(depth[A[i]] > depth[B[i]]) low[i] = A[i];
        else low[i] = B[i];
    }
}

int DP[502];

void dfs2(int x, int par = -1){
    for(auto y: link[x]){
        if(y == par) continue;
        DP[y] += DP[x];
        dfs2(y, x);
    }
}

void Anya(int C[]){
    memset(DP, 0, sizeof(DP));
    for(int i=0; i<n-1; i++){
        DP[low[i]] = C[i];
    }
    dfs2(0);

    for(int i=0; i<n-1; i++) Save(i, C[i]);
    for(int i=0; i<n; i++){
        if(mark[i]){
            for(int j=numLoc[i]; j<numLoc[i]+9; j++){
                int x = j-numLoc[i];
                Save(j, (DP[i]>>x)&1);
            }
        }
    }
}

#include "Borislib.h"
#include <bits/stdc++.h>

using namespace std;

static int n;
static vector<int> link[502];
static bool mark[502];
static int depth[502];
static int numLoc[502], locCnt;
static int low[502], edge[502], p[502];

static int dfs(int x, int par = -1){
    int maxDepth = 0;
    for(auto y: link[x]){
        if(y == par) continue;
        depth[y] = depth[x] + 1;
        p[y] = x;
        maxDepth = max(dfs(y, x)+1, maxDepth);
    }
    if(maxDepth == 12 || x==0){
        mark[x] = 1;
        numLoc[x] = locCnt;
        locCnt += 9;
        maxDepth = 0;
    }
    return maxDepth;
}

void InitBoris(int N , int A[] , int B[]) {
    n = N;
    for(int i=0; i<N-1; i++) link[A[i]].push_back(B[i]), link[B[i]].push_back(A[i]);
    locCnt = n;
    dfs(0);
    for(int i=0; i<N-1; i++){
        if(depth[A[i]] > depth[B[i]]) low[i] = A[i];
        else low[i] = B[i];
        edge[low[i]] = i;
    }
}

int Boris(int x){
    int sum = 0;
    while(!mark[x]){
        if(Ask(edge[x])) sum++;
        x = p[x];
    }
    int base = numLoc[x];
    for(int i=0; i<9; i++){
        if(Ask(base+i)) sum += (1<<i);
    }
    return sum;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 632 KB Output is correct
2 Correct 2 ms 708 KB Output is correct
3 Correct 3 ms 684 KB Output is correct
4 Correct 3 ms 840 KB Output is correct
5 Correct 5 ms 920 KB Output is correct
6 Correct 6 ms 920 KB Output is correct
7 Correct 5 ms 920 KB Output is correct
8 Correct 6 ms 920 KB Output is correct
9 Incorrect 5 ms 912 KB Wrong Answer [6]
10 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 992 KB Output is correct
2 Incorrect 5 ms 1076 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 1716 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 1604 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -