oj.uz

Submission #591888

# Submission time Handle Problem Language Result Execution time Memory
591888 2022-07-08T06:44:50 Z 반딧불(#8422) Flights (JOI22_flights) C++17
30 / 100
 261 ms 2644 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=0; i<10; i++){
        for(int j=i; j<10; j++){
            int tmp = dist(idx[A*10+i], idx[B*10+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%10 > y%10) 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 = 0;
    int ret = 0;
    for(int a=0; a<10; a++){
        for(int b=a; b<10; b++){
            if(a == x%10 && b == y%10) goto nextstep;
            st += 14;
        }
    }
    nextstep:
    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 0 ms 656 KB Output is correct
3 Correct 0 ms 656 KB Output is correct
4 Correct 1 ms 656 KB Output is correct
5 Correct 0 ms 656 KB Output is correct
6 Correct 7 ms 1916 KB Output is correct
7 Correct 6 ms 1920 KB Output is correct
8 Correct 7 ms 1932 KB Output is correct
9 Correct 7 ms 2012 KB Output is correct
10 Correct 8 ms 2044 KB Output is correct
11 Correct 7 ms 1756 KB Output is correct
12 Correct 7 ms 1916 KB Output is correct
13 Correct 8 ms 1916 KB Output is correct
14 Correct 6 ms 1928 KB Output is correct
15 Correct 7 ms 2640 KB Output is correct
16 Correct 6 ms 2128 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 748 KB Output is partially correct
2 Partially correct 47 ms 2572 KB Output is partially correct
3 Partially correct 3 ms 748 KB Output is partially correct
4 Partially correct 233 ms 1928 KB Output is partially correct
5 Partially correct 208 ms 2064 KB Output is partially correct
6 Partially correct 204 ms 2008 KB Output is partially correct
7 Partially correct 221 ms 2596 KB Output is partially correct
8 Partially correct 215 ms 2112 KB Output is partially correct
9 Partially correct 201 ms 2252 KB Output is partially correct
10 Partially correct 203 ms 2352 KB Output is partially correct
11 Partially correct 204 ms 2032 KB Output is partially correct
12 Partially correct 26 ms 1732 KB Output is partially correct
13 Partially correct 123 ms 1944 KB Output is partially correct
14 Partially correct 124 ms 2028 KB Output is partially correct
15 Partially correct 6 ms 784 KB Output is partially correct
16 Partially correct 190 ms 2644 KB Output is partially correct
17 Partially correct 207 ms 2564 KB Output is partially correct
18 Partially correct 191 ms 2512 KB Output is partially correct
19 Partially correct 186 ms 2436 KB Output is partially correct
20 Partially correct 174 ms 2352 KB Output is partially correct
21 Partially correct 194 ms 2552 KB Output is partially correct
22 Partially correct 212 ms 2144 KB Output is partially correct
23 Partially correct 212 ms 2064 KB Output is partially correct
24 Partially correct 243 ms 2052 KB Output is partially correct
25 Partially correct 199 ms 2068 KB Output is partially correct
26 Partially correct 192 ms 1984 KB Output is partially correct
27 Partially correct 230 ms 2164 KB Output is partially correct
28 Partially correct 188 ms 2056 KB Output is partially correct
29 Partially correct 221 ms 1968 KB Output is partially correct
30 Partially correct 212 ms 2052 KB Output is partially correct
31 Partially correct 210 ms 2088 KB Output is partially correct
32 Partially correct 238 ms 2008 KB Output is partially correct
33 Partially correct 217 ms 2100 KB Output is partially correct
34 Partially correct 193 ms 1972 KB Output is partially correct
35 Partially correct 202 ms 2256 KB Output is partially correct
36 Partially correct 211 ms 1964 KB Output is partially correct
37 Partially correct 202 ms 2100 KB Output is partially correct
38 Partially correct 215 ms 2052 KB Output is partially correct
39 Partially correct 42 ms 2020 KB Output is partially correct
40 Partially correct 261 ms 2432 KB Output is partially correct