oj.uz

Submission #591887

# Submission time Handle Problem Language Result Execution time Memory
591887 2022-07-08T06:42:13 Z 반딧불(#8422) Flights (JOI22_flights) C++17
21 / 100
 297 ms 2680 KB 
#include "Ali.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace {
    int n;
    int in[10002], idx[10002], inCnt;
    vector<int> link[10002];
    string str;

    int par[10002], LCADB[10002][14], depth[10002];

    void dfs(int x, int p=-1){
        in[x] = inCnt++;
        idx[in[x]] = x;
        SetID(x, in[x]);
        if(p!=-1){
            par[x] = p;
            link[x].erase(find(link[x].begin(), link[x].end(), p));
        }
        str.push_back('1');
        for(auto y: link[x]){
            depth[y] = depth[x]+1;
            dfs(y, x);
        }
        str.push_back('0');
    }

    int getLCA(int x, int y){
        if(depth[x] > depth[y]) swap(x, y);
        for(int d=0; d<14; d++) if((depth[y]-depth[x])&(1<<d)) y = LCADB[y][d];
        if(x==y) return x;
        for(int d=13; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
        return par[x];
    }

    int dist(int x, int y){
        return depth[x] + depth[y] - 2*depth[getLCA(x, y)];
    }
}

void Init(int N, vector<int> U, vector<int> V){
    for(int i=0; i<=n; i++){
        link[i].clear();
        in[i] = idx[i] = 0;
        par[i] = 0;
        depth[i] = 0;
        for(int j=0; j<14; j++) LCADB[i][j] = 0;
    }

    n = N;
    inCnt = 0;
    for(int i=0; i<n-1; i++) link[U[i]].push_back(V[i]), link[V[i]].push_back(U[i]);
    str.clear();

    dfs(0);
    for(int i=0; i<n; i++) LCADB[i][0] = par[i];
    for(int d=1; d<14; d++) for(int i=0; i<n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];
}

string SendA(string S){
    ll A = 0, B = 0;
    for(int i=0; i<10; i++) if(S[i] == '1') A += (1<<i);
    for(int i=0; i<10; i++) if(S[i+10] == '1') B += (1<<i);
    string ret;
    for(int i=A*10; i<A*10+10; i++){
        for(int j=B*10; j<B*10+10; j++){
            int tmp = dist(idx[i], idx[j]);
            for(int x=0; x<14; x++) ret.push_back((tmp&(1<<x)) ? '1' : '0');
        }
    }
    return ret;
}

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

using namespace std;

typedef long long ll;

namespace {
    int n, x, y;
}

string SendB(int N, int X, int Y){
    n = N, x = X, y = Y;
    if(x>y) swap(x, y);
    string ret;
    for(int i=0; i<10; i++) ret.push_back(((x/10)&(1<<i)) ? '1' : '0');
    for(int i=0; i<10; i++) ret.push_back(((y/10)&(1<<i)) ? '1' : '0');
    return ret;
}

int Answer(string T){
    int st = 14 * ((x%10)*10 + y%10);
    int ret = 0;
    for(int i=0; i<14; i++) if(T[st+i] == '1') ret += (1<<i);
    return ret;
}

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 656 KB Output is correct
2 Correct 2 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 2 ms 756 KB Output is correct
6 Correct 6 ms 1924 KB Output is correct
7 Correct 6 ms 1956 KB Output is correct
8 Correct 8 ms 2064 KB Output is correct
9 Correct 7 ms 2012 KB Output is correct
10 Correct 7 ms 2104 KB Output is correct
11 Correct 7 ms 1664 KB Output is correct
12 Correct 7 ms 1924 KB Output is correct
13 Correct 7 ms 2008 KB Output is correct
14 Correct 7 ms 1900 KB Output is correct
15 Correct 6 ms 2652 KB Output is correct
16 Correct 9 ms 1916 KB Output is correct

Subtask #2
6.0 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 656 KB Output is partially correct
2 Partially correct 47 ms 2620 KB Output is partially correct
3 Partially correct 3 ms 748 KB Output is partially correct
4 Partially correct 297 ms 1956 KB Output is partially correct
5 Partially correct 241 ms 2016 KB Output is partially correct
6 Partially correct 209 ms 1940 KB Output is partially correct
7 Partially correct 249 ms 2616 KB Output is partially correct
8 Partially correct 226 ms 2064 KB Output is partially correct
9 Partially correct 196 ms 2356 KB Output is partially correct
10 Partially correct 233 ms 2444 KB Output is partially correct
11 Partially correct 202 ms 2104 KB Output is partially correct
12 Partially correct 31 ms 1740 KB Output is partially correct
13 Partially correct 134 ms 1948 KB Output is partially correct
14 Partially correct 150 ms 2068 KB Output is partially correct
15 Partially correct 7 ms 780 KB Output is partially correct
16 Partially correct 209 ms 2680 KB Output is partially correct
17 Partially correct 210 ms 2656 KB Output is partially correct
18 Partially correct 212 ms 2588 KB Output is partially correct
19 Partially correct 188 ms 2504 KB Output is partially correct
20 Partially correct 143 ms 2252 KB Output is partially correct
21 Partially correct 222 ms 2400 KB Output is partially correct
22 Partially correct 201 ms 2056 KB Output is partially correct
23 Partially correct 220 ms 2144 KB Output is partially correct
24 Partially correct 189 ms 2112 KB Output is partially correct
25 Partially correct 229 ms 2224 KB Output is partially correct
26 Partially correct 195 ms 2048 KB Output is partially correct
27 Partially correct 206 ms 2064 KB Output is partially correct
28 Partially correct 204 ms 2068 KB Output is partially correct
29 Partially correct 217 ms 2132 KB Output is partially correct
30 Partially correct 208 ms 2060 KB Output is partially correct
31 Partially correct 189 ms 2084 KB Output is partially correct
32 Partially correct 204 ms 2112 KB Output is partially correct
33 Partially correct 207 ms 2016 KB Output is partially correct
34 Partially correct 194 ms 2072 KB Output is partially correct
35 Partially correct 227 ms 1992 KB Output is partially correct
36 Partially correct 220 ms 2064 KB Output is partially correct
37 Partially correct 237 ms 2072 KB Output is partially correct
38 Partially correct 203 ms 2008 KB Output is partially correct
39 Partially correct 34 ms 1948 KB Output is partially correct
40 Partially correct 251 ms 2552 KB Output is partially correct