oj.uz

Submission #578017

# Submission time Handle Problem Language Result Execution time Memory
578017 2022-06-15T18:56:05 Z 2fat2code Saveit (IOI10_saveit) C++17
0 / 100
 284 ms 10852 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++){
            p[i] += decode_bit() * (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 284 ms 10852 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 60 call(s) of encode_bit()
3 Incorrect 19 ms 5724 KB wrong parameter
4 Correct 3 ms 4604 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 27 ms 5992 KB wrong parameter
6 Incorrect 23 ms 6132 KB wrong parameter
7 Incorrect 48 ms 6324 KB wrong parameter
8 Incorrect 20 ms 6016 KB wrong parameter
9 Incorrect 22 ms 5968 KB wrong parameter
10 Incorrect 24 ms 6136 KB wrong parameter
11 Incorrect 28 ms 6016 KB wrong parameter
12 Incorrect 24 ms 5960 KB wrong parameter
13 Incorrect 42 ms 6552 KB wrong parameter
14 Incorrect 19 ms 5896 KB wrong parameter
15 Incorrect 20 ms 6020 KB wrong parameter
16 Incorrect 67 ms 6376 KB wrong parameter
17 Incorrect 39 ms 6400 KB wrong parameter
18 Incorrect 45 ms 6604 KB wrong parameter
19 Incorrect 37 ms 6248 KB wrong parameter
20 Incorrect 53 ms 7000 KB wrong parameter
21 Incorrect 61 ms 7208 KB wrong parameter
22 Incorrect 43 ms 6576 KB wrong parameter
23 Incorrect 69 ms 7296 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 10852 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 60 call(s) of encode_bit()
3 Incorrect 19 ms 5724 KB wrong parameter
4 Correct 3 ms 4604 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 27 ms 5992 KB wrong parameter
6 Incorrect 23 ms 6132 KB wrong parameter
7 Incorrect 48 ms 6324 KB wrong parameter
8 Incorrect 20 ms 6016 KB wrong parameter
9 Incorrect 22 ms 5968 KB wrong parameter
10 Incorrect 24 ms 6136 KB wrong parameter
11 Incorrect 28 ms 6016 KB wrong parameter
12 Incorrect 24 ms 5960 KB wrong parameter
13 Incorrect 42 ms 6552 KB wrong parameter
14 Incorrect 19 ms 5896 KB wrong parameter
15 Incorrect 20 ms 6020 KB wrong parameter
16 Incorrect 67 ms 6376 KB wrong parameter
17 Incorrect 39 ms 6400 KB wrong parameter
18 Incorrect 45 ms 6604 KB wrong parameter
19 Incorrect 37 ms 6248 KB wrong parameter
20 Incorrect 53 ms 7000 KB wrong parameter
21 Incorrect 61 ms 7208 KB wrong parameter
22 Incorrect 43 ms 6576 KB wrong parameter
23 Incorrect 69 ms 7296 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 10852 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 60 call(s) of encode_bit()
3 Incorrect 19 ms 5724 KB wrong parameter
4 Correct 3 ms 4604 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 27 ms 5992 KB wrong parameter
6 Incorrect 23 ms 6132 KB wrong parameter
7 Incorrect 48 ms 6324 KB wrong parameter
8 Incorrect 20 ms 6016 KB wrong parameter
9 Incorrect 22 ms 5968 KB wrong parameter
10 Incorrect 24 ms 6136 KB wrong parameter
11 Incorrect 28 ms 6016 KB wrong parameter
12 Incorrect 24 ms 5960 KB wrong parameter
13 Incorrect 42 ms 6552 KB wrong parameter
14 Incorrect 19 ms 5896 KB wrong parameter
15 Incorrect 20 ms 6020 KB wrong parameter
16 Incorrect 67 ms 6376 KB wrong parameter
17 Incorrect 39 ms 6400 KB wrong parameter
18 Incorrect 45 ms 6604 KB wrong parameter
19 Incorrect 37 ms 6248 KB wrong parameter
20 Incorrect 53 ms 7000 KB wrong parameter
21 Incorrect 61 ms 7208 KB wrong parameter
22 Incorrect 43 ms 6576 KB wrong parameter
23 Incorrect 69 ms 7296 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 10852 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 60 call(s) of encode_bit()
3 Incorrect 19 ms 5724 KB wrong parameter
4 Correct 3 ms 4604 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 27 ms 5992 KB wrong parameter
6 Incorrect 23 ms 6132 KB wrong parameter
7 Incorrect 48 ms 6324 KB wrong parameter
8 Incorrect 20 ms 6016 KB wrong parameter
9 Incorrect 22 ms 5968 KB wrong parameter
10 Incorrect 24 ms 6136 KB wrong parameter
11 Incorrect 28 ms 6016 KB wrong parameter
12 Incorrect 24 ms 5960 KB wrong parameter
13 Incorrect 42 ms 6552 KB wrong parameter
14 Incorrect 19 ms 5896 KB wrong parameter
15 Incorrect 20 ms 6020 KB wrong parameter
16 Incorrect 67 ms 6376 KB wrong parameter
17 Incorrect 39 ms 6400 KB wrong parameter
18 Incorrect 45 ms 6604 KB wrong parameter
19 Incorrect 37 ms 6248 KB wrong parameter
20 Incorrect 53 ms 7000 KB wrong parameter
21 Incorrect 61 ms 7208 KB wrong parameter
22 Incorrect 43 ms 6576 KB wrong parameter
23 Incorrect 69 ms 7296 KB wrong parameter