oj.uz

Submission #578023

# Submission time Handle Problem Language Result Execution time Memory
578023 2022-06-15T19:15:47 Z 2fat2code Saveit (IOI10_saveit) C++17
0 / 100
 265 ms 6156 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1005;
const int hubs = 36;

int nn, hub, dist[hubs][nmax], par[nmax], lol;
vector<int>nod[nmax];

bitset<nmax>viz;

void construct(){
    queue<int>q;
    viz.reset();
    q.push(0);
    viz[0] = 1;
    while(q.size()){
        auto it = q.front();
        q.pop();
        for(auto it1 : nod[it]){
            if(!viz[it1]){
                viz[it1] = 1;
                par[it1] = it;
                q.push(it1);
            }
        }
    }
    for(int i=1;i<nn;i++){
        for(int j=0;j<=9;j++){
            if(par[i] & (1 << j)) encode_bit(1);
            else encode_bit(0);
        }
        lol += 10;
    }
    for(int i=1;i<nn;i++){
        for(int j=0;j<hub;j+=3){
            int curr = 0;
            if(dist[j][i] == dist[j][par[i]]){
                 curr += 1;
            }
            else if(dist[j][i] > dist[j][par[i]]){
                 curr += 2;
            }
            curr *= 3;
            if(j + 1 <= hub - 1){
                if(dist[j+1][i] == dist[j+1][par[i]]){
                    curr += 1;
                }
                else if(dist[j+1][i] > dist[j+1][par[i]]){
                    curr += 2;
                }
            }
            curr *= 3;
            if(j + 2 <= hub - 1){
                if(dist[j+2][i] == dist[j+2][par[i]]){
                    curr += 1;
                }
                else if(dist[j+2][i] > dist[j+2][par[i]]){
                    curr += 2;
                }
            }
            for(int t=0;t<5;t++){
                encode_bit(curr % 2);
                curr /= 2;
            }
            lol += 5;
        }
    }
    cout << lol;
}

void encode(int n, int h, int m, int v1[], int v2[]){
    nn = n; hub = h;
    for(int i=0;i<m;i++){
        nod[v1[i]].push_back(v2[i]);
        nod[v2[i]].push_back(v1[i]);
    }
    for(int i=0;i<h;i++){
        queue<int>q;
        viz.reset();
        q.push(i);
        viz[i] = 1;
        while(q.size()){
            auto it = q.front();
            q.pop();
            for(auto it1 : nod[it]){
                if(!viz[it1]){
                    dist[i][it1] = dist[i][it] + 1;
                    viz[it1] = 1;
                    q.push(it1);
                }
            }
        }
    }
    construct();
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
using namespace std;

const int nmax = 1005;
const int hubs = 36;

int p[nmax], dust[hubs][nmax];
vector <int> nid[nmax];
bitset <nmax> vuz;
vector <int> bits[nmax];

void dfs(int s){
    vuz[s] = 1;
    for(auto it : nid[s]){
        if(!vuz[it]){
            dust[0][it] = dust[0][s] + 1;
            dfs(it);
        }
    }
}

void decode(int n, int h) {
    for(int i=1;i<n;i++){
        for(int j=0;j<=9;j++){
            int heh = decode_bit();
            p[i] += heh * (1 << j);
        }
    }
    for(int i=1;i<n;i++){
        nid[p[i]].push_back(i);
    }
    for(int i=1;i<n;i++){
        for(int j=0;j<h;j+=3){
            bits[i].push_back(decode_bit());
            bits[i].push_back(decode_bit());
            bits[i].push_back(decode_bit());
            bits[i].push_back(decode_bit());
            bits[i].push_back(decode_bit());
        }
    }
    dfs(0);
    for(int i=0;i<h;i++) dust[i][0] = dust[0][i];
    for(int i=0;i<n;i++){
        for(auto it : nid[i]){
            int curr = 0;
            for(int j=0;j<h;j+=3){
                int lol = bits[it][curr] + 2*bits[it][curr+1] + 4*bits[it][curr+2] + 8*bits[it][curr+3] + 16*bits[it][curr+4];
                curr += 5;
                if(j + 2 < h){
                    int suka = lol % 3;
                    if(suka == 0){
                        dust[j+2][it] = dust[j+2][i] - 1;
                    }
                    else if(suka == 1) dust[j+2][it] = dust[j+2][i];
                    else if(suka == 2){
                        dust[j+2][it] = dust[j+2][i] + 1;
                    }
                }
                lol /= 3;
                if(j + 1 < h){
                    int suka = lol % 3;
                    if(suka == 0){
                        dust[j+1][it] = dust[j+1][i] - 1;
                    }
                    else if(suka == 1) dust[j+1][it] = dust[j+1][i];
                    else if(suka == 2){
                        dust[j+1][it] = dust[j+1][i] + 1;
                    }
                }
                lol /= 3;
                if(j < h){
                    int suka = lol % 3;
                    if(suka == 0){
                        dust[j][it] = dust[j][i] - 1;
                    }
                    else if(suka == 1) dust[j][it] = dust[j][i];
                    else if(suka == 2){
                        dust[j][it] = dust[j][i] + 1;
                    }
                }
                lol /= 3;
            }
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<n;j++){
            hops(i, j, dust[i][j]);
        }
    }

}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 265 ms 6156 KB Do not print anything to standard output: 69930DECODED_PERfeCT
2 Incorrect 0 ms 768 KB Do not print anything to standard output: 60DECODED_PERfeCT
3 Incorrect 10 ms 1404 KB Do not print anything to standard output: 62930DECODED_PERfeCT
4 Incorrect 0 ms 772 KB Do not print anything to standard output: 80DECODED_PERfeCT
5 Incorrect 13 ms 1464 KB Do not print anything to standard output: 62930DECODED_PERfeCT
6 Incorrect 16 ms 1632 KB Do not print anything to standard output: 69930DECODED_PERfeCT
7 Incorrect 40 ms 1856 KB Do not print anything to standard output: 69930DECODED_PERfeCT
8 Incorrect 11 ms 1396 KB Do not print anything to standard output: 67200DECODED_PERfeCT
9 Incorrect 11 ms 1316 KB Do not print anything to standard output: 69930DECODED_PERfeCT
10 Incorrect 15 ms 1384 KB Do not print anything to standard output: 69930DECODED_PERfeCT
11 Incorrect 14 ms 1492 KB Do not print anything to standard output: 69930DECODED_PERfeCT
12 Incorrect 10 ms 1252 KB Do not print anything to standard output: 69930DECODED_PERfeCT
13 Incorrect 50 ms 1944 KB Do not print anything to standard output: 69930DECODED_PERfeCT
14 Incorrect 14 ms 1344 KB Do not print anything to standard output: 69930DECODED_PERfeCT
15 Incorrect 16 ms 1404 KB Do not print anything to standard output: 69930DECODED_PERfeCT
16 Incorrect 36 ms 1888 KB Do not print anything to standard output: 69930DECODED_PERfeCT
17 Incorrect 38 ms 1780 KB Do not print anything to standard output: 69930DECODED_PERfeCT
18 Incorrect 36 ms 2152 KB Do not print anything to standard output: 69930DECODED_PERfeCT
19 Incorrect 24 ms 1640 KB Do not print anything to standard output: 69930DECODED_PERfeCT
20 Incorrect 48 ms 2332 KB Do not print anything to standard output: 69930DECODED_PERfeCT
21 Incorrect 77 ms 2420 KB Do not print anything to standard output: 69930DECODED_PERfeCT
22 Incorrect 34 ms 1972 KB Do not print anything to standard output: 69930DECODED_PERfeCT
23 Incorrect 54 ms 2712 KB Do not print anything to standard output: 69930DECODED_PERfeCT

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 265 ms 6156 KB Do not print anything to standard output: 69930DECODED_PERfeCT
2 Incorrect 0 ms 768 KB Do not print anything to standard output: 60DECODED_PERfeCT
3 Incorrect 10 ms 1404 KB Do not print anything to standard output: 62930DECODED_PERfeCT
4 Incorrect 0 ms 772 KB Do not print anything to standard output: 80DECODED_PERfeCT
5 Incorrect 13 ms 1464 KB Do not print anything to standard output: 62930DECODED_PERfeCT
6 Incorrect 16 ms 1632 KB Do not print anything to standard output: 69930DECODED_PERfeCT
7 Incorrect 40 ms 1856 KB Do not print anything to standard output: 69930DECODED_PERfeCT
8 Incorrect 11 ms 1396 KB Do not print anything to standard output: 67200DECODED_PERfeCT
9 Incorrect 11 ms 1316 KB Do not print anything to standard output: 69930DECODED_PERfeCT
10 Incorrect 15 ms 1384 KB Do not print anything to standard output: 69930DECODED_PERfeCT
11 Incorrect 14 ms 1492 KB Do not print anything to standard output: 69930DECODED_PERfeCT
12 Incorrect 10 ms 1252 KB Do not print anything to standard output: 69930DECODED_PERfeCT
13 Incorrect 50 ms 1944 KB Do not print anything to standard output: 69930DECODED_PERfeCT
14 Incorrect 14 ms 1344 KB Do not print anything to standard output: 69930DECODED_PERfeCT
15 Incorrect 16 ms 1404 KB Do not print anything to standard output: 69930DECODED_PERfeCT
16 Incorrect 36 ms 1888 KB Do not print anything to standard output: 69930DECODED_PERfeCT
17 Incorrect 38 ms 1780 KB Do not print anything to standard output: 69930DECODED_PERfeCT
18 Incorrect 36 ms 2152 KB Do not print anything to standard output: 69930DECODED_PERfeCT
19 Incorrect 24 ms 1640 KB Do not print anything to standard output: 69930DECODED_PERfeCT
20 Incorrect 48 ms 2332 KB Do not print anything to standard output: 69930DECODED_PERfeCT
21 Incorrect 77 ms 2420 KB Do not print anything to standard output: 69930DECODED_PERfeCT
22 Incorrect 34 ms 1972 KB Do not print anything to standard output: 69930DECODED_PERfeCT
23 Incorrect 54 ms 2712 KB Do not print anything to standard output: 69930DECODED_PERfeCT

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 265 ms 6156 KB Do not print anything to standard output: 69930DECODED_PERfeCT
2 Incorrect 0 ms 768 KB Do not print anything to standard output: 60DECODED_PERfeCT
3 Incorrect 10 ms 1404 KB Do not print anything to standard output: 62930DECODED_PERfeCT
4 Incorrect 0 ms 772 KB Do not print anything to standard output: 80DECODED_PERfeCT
5 Incorrect 13 ms 1464 KB Do not print anything to standard output: 62930DECODED_PERfeCT
6 Incorrect 16 ms 1632 KB Do not print anything to standard output: 69930DECODED_PERfeCT
7 Incorrect 40 ms 1856 KB Do not print anything to standard output: 69930DECODED_PERfeCT
8 Incorrect 11 ms 1396 KB Do not print anything to standard output: 67200DECODED_PERfeCT
9 Incorrect 11 ms 1316 KB Do not print anything to standard output: 69930DECODED_PERfeCT
10 Incorrect 15 ms 1384 KB Do not print anything to standard output: 69930DECODED_PERfeCT
11 Incorrect 14 ms 1492 KB Do not print anything to standard output: 69930DECODED_PERfeCT
12 Incorrect 10 ms 1252 KB Do not print anything to standard output: 69930DECODED_PERfeCT
13 Incorrect 50 ms 1944 KB Do not print anything to standard output: 69930DECODED_PERfeCT
14 Incorrect 14 ms 1344 KB Do not print anything to standard output: 69930DECODED_PERfeCT
15 Incorrect 16 ms 1404 KB Do not print anything to standard output: 69930DECODED_PERfeCT
16 Incorrect 36 ms 1888 KB Do not print anything to standard output: 69930DECODED_PERfeCT
17 Incorrect 38 ms 1780 KB Do not print anything to standard output: 69930DECODED_PERfeCT
18 Incorrect 36 ms 2152 KB Do not print anything to standard output: 69930DECODED_PERfeCT
19 Incorrect 24 ms 1640 KB Do not print anything to standard output: 69930DECODED_PERfeCT
20 Incorrect 48 ms 2332 KB Do not print anything to standard output: 69930DECODED_PERfeCT
21 Incorrect 77 ms 2420 KB Do not print anything to standard output: 69930DECODED_PERfeCT
22 Incorrect 34 ms 1972 KB Do not print anything to standard output: 69930DECODED_PERfeCT
23 Incorrect 54 ms 2712 KB Do not print anything to standard output: 69930DECODED_PERfeCT

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 265 ms 6156 KB Do not print anything to standard output: 69930DECODED_PERfeCT
2 Incorrect 0 ms 768 KB Do not print anything to standard output: 60DECODED_PERfeCT
3 Incorrect 10 ms 1404 KB Do not print anything to standard output: 62930DECODED_PERfeCT
4 Incorrect 0 ms 772 KB Do not print anything to standard output: 80DECODED_PERfeCT
5 Incorrect 13 ms 1464 KB Do not print anything to standard output: 62930DECODED_PERfeCT
6 Incorrect 16 ms 1632 KB Do not print anything to standard output: 69930DECODED_PERfeCT
7 Incorrect 40 ms 1856 KB Do not print anything to standard output: 69930DECODED_PERfeCT
8 Incorrect 11 ms 1396 KB Do not print anything to standard output: 67200DECODED_PERfeCT
9 Incorrect 11 ms 1316 KB Do not print anything to standard output: 69930DECODED_PERfeCT
10 Incorrect 15 ms 1384 KB Do not print anything to standard output: 69930DECODED_PERfeCT
11 Incorrect 14 ms 1492 KB Do not print anything to standard output: 69930DECODED_PERfeCT
12 Incorrect 10 ms 1252 KB Do not print anything to standard output: 69930DECODED_PERfeCT
13 Incorrect 50 ms 1944 KB Do not print anything to standard output: 69930DECODED_PERfeCT
14 Incorrect 14 ms 1344 KB Do not print anything to standard output: 69930DECODED_PERfeCT
15 Incorrect 16 ms 1404 KB Do not print anything to standard output: 69930DECODED_PERfeCT
16 Incorrect 36 ms 1888 KB Do not print anything to standard output: 69930DECODED_PERfeCT
17 Incorrect 38 ms 1780 KB Do not print anything to standard output: 69930DECODED_PERfeCT
18 Incorrect 36 ms 2152 KB Do not print anything to standard output: 69930DECODED_PERfeCT
19 Incorrect 24 ms 1640 KB Do not print anything to standard output: 69930DECODED_PERfeCT
20 Incorrect 48 ms 2332 KB Do not print anything to standard output: 69930DECODED_PERfeCT
21 Incorrect 77 ms 2420 KB Do not print anything to standard output: 69930DECODED_PERfeCT
22 Incorrect 34 ms 1972 KB Do not print anything to standard output: 69930DECODED_PERfeCT
23 Incorrect 54 ms 2712 KB Do not print anything to standard output: 69930DECODED_PERfeCT