oj.uz

답안 #567830

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
567830 2022-05-24T08:56:07 Z tqbfjotld Flights (JOI22_flights) C++17
33 / 100
 294 ms 2744 KB 
#include "Ali.h"
#include <bits/stdc++.h>

namespace {

std::vector<int> adjl[10005];
int p[10005][18];
int dep[10005];
void dfs1(int node, int pa){
    p[node][0] = pa;
    for (auto x : adjl[node]){
        if (x==pa) continue;
        dep[x] = dep[node]+1;
        dfs1(x,node);
    }
}
int lca(int a, int b){
    if (dep[a]>dep[b]) std::swap(a,b);
    int t = dep[b]-dep[a];
    for (int x = 0; x<18; x++){
        if (t&(1<<x)) b = p[b][x];
    }
    if (a==b) return a;
    for (int x = 17; x>=0; x--){
        if (p[a][x]!=p[b][x]){
            a = p[a][x];
            b = p[b][x];
        }
    }
    return p[a][0];
}
int n;
int getdist(int a, int b){
    if (a>=n || b>=n) return 0;
    return dep[a]+dep[b]-2*dep[lca(a,b)];
}

}

void Init(int N, std::vector<int> U, std::vector<int> V) {
    for (int x = 0; x<N; x++){
        adjl[x].clear();
    }
    for (int x = 0; x<N-1; x++){
        adjl[U[x]].push_back(V[x]);
        adjl[V[x]].push_back(U[x]);
    }
    dfs1(0,-1);
    n = N;
    for (int x = 0; x<N; x++){
        SetID(x,2*x+(dep[x]&1));
    }
    for (int x = 1; x<18; x++){
        for (int y = 0; y<N; y++){
            if (p[y][x-1]==-1) p[y][x] = -1;
            else p[y][x] = p[p[y][x-1]][x-1];
        }
    }
}

std::string SendA(std::string S) {
    int thing = 0;
    for (int x = 0; x<20; x++){
        if (S[x]=='1') thing += 1<<x;
    }
    std::string ans;
    for (int x = thing; x<n*(n-1)/2; x+=(1<<20)){
        int l = 0;
        int r = n-1;
        while (l+1<r){
            int mid = (l+r)/2;
            if (x<(mid)*(mid+1)/2){
                r = mid;
            }
            else l = mid;
        }
        int b = r;
        int a = x-(b)*(b-1)/2;
        int t = getdist(a,b);
        //printf("push val %d %d\n",a,b);
        for (int x = 1; x<=13; x++){
            ans.push_back((t&(1<<x))?'1':'0');
        }
    }
    return ans;
}
#include "Benjamin.h"
#include <bits/stdc++.h>

namespace {

int storeX,storeY;
int storenum;

}

std::string SendB(int N, int X, int Y) {
    int n1 = X/2;
    int n2 = Y/2;
    storeX = X;
    storeY = Y;
    std::string ans;
    if (n1>n2){
        std::swap(n1,n2);
        std::swap(X,Y);
        std::swap(storeX,storeY);
    }
    int num = 0;
    for (int x = 0; x<n2; x++){
        num += x;
    }
    num += n1;
    for (int x = 0; x<20; x++){
        ans.push_back((num&(1<<x))?'1':'0');
    }
    storenum = num;
    return ans;
}

int Answer(std::string T) {
    if (storeX==storeY) return 0;
    int t = storenum>>20;
    int ans = 0;
    for (int x = 0; x<13; x++){
        if (T[t*13+x]=='1'){
            ans += (1<<x);
        }
    }
    ans<<=1;
    if ((storeX&1)!=(storeY&1)){
        ans++;
    }
    return ans;
}

Compilation message

grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 656 KB Output is correct
2 Correct 0 ms 656 KB Output is correct
3 Correct 2 ms 656 KB Output is correct
4 Correct 1 ms 656 KB Output is correct
5 Correct 1 ms 656 KB Output is correct
6 Correct 8 ms 1880 KB Output is correct
7 Correct 9 ms 1960 KB Output is correct
8 Correct 7 ms 2020 KB Output is correct
9 Correct 9 ms 2020 KB Output is correct
10 Correct 6 ms 2148 KB Output is correct
11 Correct 6 ms 1680 KB Output is correct
12 Correct 7 ms 2064 KB Output is correct
13 Correct 8 ms 1936 KB Output is correct
14 Correct 8 ms 1936 KB Output is correct
15 Correct 8 ms 2576 KB Output is correct
16 Correct 7 ms 2148 KB Output is correct

Subtask #2
18.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 656 KB Output is correct
2 Partially correct 46 ms 2720 KB Output is partially correct
3 Correct 5 ms 656 KB Output is correct
4 Partially correct 251 ms 2100 KB Output is partially correct
5 Partially correct 265 ms 2096 KB Output is partially correct
6 Partially correct 220 ms 2272 KB Output is partially correct
7 Partially correct 231 ms 2632 KB Output is partially correct
8 Partially correct 294 ms 2128 KB Output is partially correct
9 Partially correct 223 ms 2488 KB Output is partially correct
10 Partially correct 231 ms 2324 KB Output is partially correct
11 Partially correct 219 ms 2088 KB Output is partially correct
12 Partially correct 27 ms 1784 KB Output is partially correct
13 Partially correct 195 ms 2092 KB Output is partially correct
14 Partially correct 180 ms 2200 KB Output is partially correct
15 Correct 5 ms 764 KB Output is correct
16 Partially correct 256 ms 2744 KB Output is partially correct
17 Partially correct 265 ms 2736 KB Output is partially correct
18 Partially correct 201 ms 2568 KB Output is partially correct
19 Partially correct 209 ms 2616 KB Output is partially correct
20 Partially correct 169 ms 2332 KB Output is partially correct
21 Partially correct 224 ms 2532 KB Output is partially correct
22 Partially correct 188 ms 2120 KB Output is partially correct
23 Partially correct 214 ms 2096 KB Output is partially correct
24 Partially correct 239 ms 2200 KB Output is partially correct
25 Partially correct 227 ms 2048 KB Output is partially correct
26 Partially correct 268 ms 2112 KB Output is partially correct
27 Partially correct 242 ms 2076 KB Output is partially correct
28 Partially correct 228 ms 2252 KB Output is partially correct
29 Partially correct 194 ms 2144 KB Output is partially correct
30 Partially correct 264 ms 2188 KB Output is partially correct
31 Partially correct 242 ms 2176 KB Output is partially correct
32 Partially correct 245 ms 2108 KB Output is partially correct
33 Partially correct 194 ms 2040 KB Output is partially correct
34 Partially correct 220 ms 2044 KB Output is partially correct
35 Partially correct 201 ms 2200 KB Output is partially correct
36 Partially correct 192 ms 2124 KB Output is partially correct
37 Partially correct 220 ms 2076 KB Output is partially correct
38 Partially correct 195 ms 2200 KB Output is partially correct
39 Partially correct 34 ms 2096 KB Output is partially correct
40 Partially correct 264 ms 2548 KB Output is partially correct