oj.uz

Submission #578020

# Submission time Handle Problem Language Result Execution time Memory
578020 2022-06-15T19:10:22 Z 2fat2code Saveit (IOI10_saveit) C++17
0 / 100
 216 ms 10924 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];
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);
        }
    }
    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;
            }
        }
    }
}

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 Correct 216 ms 10924 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4600 KB Output is correct - 60 call(s) of encode_bit()
3 Incorrect 19 ms 5812 KB wrong parameter
4 Correct 2 ms 4612 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 27 ms 6036 KB wrong parameter
6 Incorrect 23 ms 6064 KB wrong parameter
7 Incorrect 37 ms 6512 KB wrong parameter
8 Incorrect 22 ms 5876 KB wrong parameter
9 Incorrect 22 ms 5968 KB wrong parameter
10 Incorrect 20 ms 6012 KB wrong parameter
11 Incorrect 24 ms 6048 KB wrong parameter
12 Incorrect 18 ms 5796 KB wrong parameter
13 Incorrect 57 ms 6596 KB wrong parameter
14 Incorrect 20 ms 5980 KB wrong parameter
15 Incorrect 23 ms 6092 KB wrong parameter
16 Incorrect 51 ms 6452 KB wrong parameter
17 Incorrect 45 ms 6464 KB wrong parameter
18 Incorrect 43 ms 6692 KB wrong parameter
19 Incorrect 30 ms 6312 KB wrong parameter
20 Incorrect 49 ms 7100 KB wrong parameter
21 Incorrect 62 ms 7148 KB wrong parameter
22 Incorrect 52 ms 6556 KB wrong parameter
23 Incorrect 96 ms 7304 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 10924 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4600 KB Output is correct - 60 call(s) of encode_bit()
3 Incorrect 19 ms 5812 KB wrong parameter
4 Correct 2 ms 4612 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 27 ms 6036 KB wrong parameter
6 Incorrect 23 ms 6064 KB wrong parameter
7 Incorrect 37 ms 6512 KB wrong parameter
8 Incorrect 22 ms 5876 KB wrong parameter
9 Incorrect 22 ms 5968 KB wrong parameter
10 Incorrect 20 ms 6012 KB wrong parameter
11 Incorrect 24 ms 6048 KB wrong parameter
12 Incorrect 18 ms 5796 KB wrong parameter
13 Incorrect 57 ms 6596 KB wrong parameter
14 Incorrect 20 ms 5980 KB wrong parameter
15 Incorrect 23 ms 6092 KB wrong parameter
16 Incorrect 51 ms 6452 KB wrong parameter
17 Incorrect 45 ms 6464 KB wrong parameter
18 Incorrect 43 ms 6692 KB wrong parameter
19 Incorrect 30 ms 6312 KB wrong parameter
20 Incorrect 49 ms 7100 KB wrong parameter
21 Incorrect 62 ms 7148 KB wrong parameter
22 Incorrect 52 ms 6556 KB wrong parameter
23 Incorrect 96 ms 7304 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 10924 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4600 KB Output is correct - 60 call(s) of encode_bit()
3 Incorrect 19 ms 5812 KB wrong parameter
4 Correct 2 ms 4612 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 27 ms 6036 KB wrong parameter
6 Incorrect 23 ms 6064 KB wrong parameter
7 Incorrect 37 ms 6512 KB wrong parameter
8 Incorrect 22 ms 5876 KB wrong parameter
9 Incorrect 22 ms 5968 KB wrong parameter
10 Incorrect 20 ms 6012 KB wrong parameter
11 Incorrect 24 ms 6048 KB wrong parameter
12 Incorrect 18 ms 5796 KB wrong parameter
13 Incorrect 57 ms 6596 KB wrong parameter
14 Incorrect 20 ms 5980 KB wrong parameter
15 Incorrect 23 ms 6092 KB wrong parameter
16 Incorrect 51 ms 6452 KB wrong parameter
17 Incorrect 45 ms 6464 KB wrong parameter
18 Incorrect 43 ms 6692 KB wrong parameter
19 Incorrect 30 ms 6312 KB wrong parameter
20 Incorrect 49 ms 7100 KB wrong parameter
21 Incorrect 62 ms 7148 KB wrong parameter
22 Incorrect 52 ms 6556 KB wrong parameter
23 Incorrect 96 ms 7304 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 10924 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4600 KB Output is correct - 60 call(s) of encode_bit()
3 Incorrect 19 ms 5812 KB wrong parameter
4 Correct 2 ms 4612 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 27 ms 6036 KB wrong parameter
6 Incorrect 23 ms 6064 KB wrong parameter
7 Incorrect 37 ms 6512 KB wrong parameter
8 Incorrect 22 ms 5876 KB wrong parameter
9 Incorrect 22 ms 5968 KB wrong parameter
10 Incorrect 20 ms 6012 KB wrong parameter
11 Incorrect 24 ms 6048 KB wrong parameter
12 Incorrect 18 ms 5796 KB wrong parameter
13 Incorrect 57 ms 6596 KB wrong parameter
14 Incorrect 20 ms 5980 KB wrong parameter
15 Incorrect 23 ms 6092 KB wrong parameter
16 Incorrect 51 ms 6452 KB wrong parameter
17 Incorrect 45 ms 6464 KB wrong parameter
18 Incorrect 43 ms 6692 KB wrong parameter
19 Incorrect 30 ms 6312 KB wrong parameter
20 Incorrect 49 ms 7100 KB wrong parameter
21 Incorrect 62 ms 7148 KB wrong parameter
22 Incorrect 52 ms 6556 KB wrong parameter
23 Incorrect 96 ms 7304 KB wrong parameter