oj.uz

Submission #577997

# Submission time Handle Problem Language Result Execution time Memory
577997 2022-06-15T18:02:21 Z 2fat2code Saveit (IOI10_saveit) C++17
0 / 100
 311 ms 10752 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 j=0;j<5;j++){
                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;
        dist[i][i] = 0;
        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++] + 4*bits[it][curr++] + 8*bits[it][curr++] + 16*bits[it][curr++];
                if(j + 2 < h){
                    int suka = lol % 3;
                    if(suka == 0){
                        dust[j+2][it] = dust[j+2][i] - 1;
                    }
                    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 == 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 == 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]);
        }
    }
}

Compilation message

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:51:105: warning: operation on 'curr' may be undefined [-Wsequence-point]
   51 |                 int lol = bits[it][curr++] + 2 * bits[it][curr++] + 4*bits[it][curr++] + 8*bits[it][curr++] + 16*bits[it][curr++];
      |                                                                                                     ~~~~^~
decoder.cpp:51:105: warning: operation on 'curr' may be undefined [-Wsequence-point]
decoder.cpp:51:105: warning: operation on 'curr' may be undefined [-Wsequence-point]
decoder.cpp:51:105: warning: operation on 'curr' may be undefined [-Wsequence-point]

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 311 ms 10752 KB wrong parameter
2 Incorrect 3 ms 4604 KB Output isn't correct
3 Incorrect 19 ms 5888 KB wrong parameter
4 Incorrect 3 ms 4604 KB Output isn't correct
5 Incorrect 26 ms 5924 KB wrong parameter
6 Incorrect 25 ms 6120 KB wrong parameter
7 Incorrect 36 ms 6324 KB wrong parameter
8 Incorrect 19 ms 5884 KB wrong parameter
9 Incorrect 19 ms 5936 KB wrong parameter
10 Incorrect 20 ms 6048 KB wrong parameter
11 Incorrect 23 ms 6180 KB wrong parameter
12 Incorrect 24 ms 5904 KB wrong parameter
13 Incorrect 45 ms 6504 KB wrong parameter
14 Incorrect 19 ms 5940 KB wrong parameter
15 Incorrect 26 ms 5952 KB wrong parameter
16 Incorrect 52 ms 6452 KB wrong parameter
17 Incorrect 34 ms 6412 KB wrong parameter
18 Incorrect 43 ms 6676 KB wrong parameter
19 Incorrect 32 ms 6276 KB wrong parameter
20 Incorrect 69 ms 6960 KB wrong parameter
21 Incorrect 92 ms 7016 KB wrong parameter
22 Incorrect 45 ms 6536 KB wrong parameter
23 Incorrect 65 ms 7220 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 311 ms 10752 KB wrong parameter
2 Incorrect 3 ms 4604 KB Output isn't correct
3 Incorrect 19 ms 5888 KB wrong parameter
4 Incorrect 3 ms 4604 KB Output isn't correct
5 Incorrect 26 ms 5924 KB wrong parameter
6 Incorrect 25 ms 6120 KB wrong parameter
7 Incorrect 36 ms 6324 KB wrong parameter
8 Incorrect 19 ms 5884 KB wrong parameter
9 Incorrect 19 ms 5936 KB wrong parameter
10 Incorrect 20 ms 6048 KB wrong parameter
11 Incorrect 23 ms 6180 KB wrong parameter
12 Incorrect 24 ms 5904 KB wrong parameter
13 Incorrect 45 ms 6504 KB wrong parameter
14 Incorrect 19 ms 5940 KB wrong parameter
15 Incorrect 26 ms 5952 KB wrong parameter
16 Incorrect 52 ms 6452 KB wrong parameter
17 Incorrect 34 ms 6412 KB wrong parameter
18 Incorrect 43 ms 6676 KB wrong parameter
19 Incorrect 32 ms 6276 KB wrong parameter
20 Incorrect 69 ms 6960 KB wrong parameter
21 Incorrect 92 ms 7016 KB wrong parameter
22 Incorrect 45 ms 6536 KB wrong parameter
23 Incorrect 65 ms 7220 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 311 ms 10752 KB wrong parameter
2 Incorrect 3 ms 4604 KB Output isn't correct
3 Incorrect 19 ms 5888 KB wrong parameter
4 Incorrect 3 ms 4604 KB Output isn't correct
5 Incorrect 26 ms 5924 KB wrong parameter
6 Incorrect 25 ms 6120 KB wrong parameter
7 Incorrect 36 ms 6324 KB wrong parameter
8 Incorrect 19 ms 5884 KB wrong parameter
9 Incorrect 19 ms 5936 KB wrong parameter
10 Incorrect 20 ms 6048 KB wrong parameter
11 Incorrect 23 ms 6180 KB wrong parameter
12 Incorrect 24 ms 5904 KB wrong parameter
13 Incorrect 45 ms 6504 KB wrong parameter
14 Incorrect 19 ms 5940 KB wrong parameter
15 Incorrect 26 ms 5952 KB wrong parameter
16 Incorrect 52 ms 6452 KB wrong parameter
17 Incorrect 34 ms 6412 KB wrong parameter
18 Incorrect 43 ms 6676 KB wrong parameter
19 Incorrect 32 ms 6276 KB wrong parameter
20 Incorrect 69 ms 6960 KB wrong parameter
21 Incorrect 92 ms 7016 KB wrong parameter
22 Incorrect 45 ms 6536 KB wrong parameter
23 Incorrect 65 ms 7220 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 311 ms 10752 KB wrong parameter
2 Incorrect 3 ms 4604 KB Output isn't correct
3 Incorrect 19 ms 5888 KB wrong parameter
4 Incorrect 3 ms 4604 KB Output isn't correct
5 Incorrect 26 ms 5924 KB wrong parameter
6 Incorrect 25 ms 6120 KB wrong parameter
7 Incorrect 36 ms 6324 KB wrong parameter
8 Incorrect 19 ms 5884 KB wrong parameter
9 Incorrect 19 ms 5936 KB wrong parameter
10 Incorrect 20 ms 6048 KB wrong parameter
11 Incorrect 23 ms 6180 KB wrong parameter
12 Incorrect 24 ms 5904 KB wrong parameter
13 Incorrect 45 ms 6504 KB wrong parameter
14 Incorrect 19 ms 5940 KB wrong parameter
15 Incorrect 26 ms 5952 KB wrong parameter
16 Incorrect 52 ms 6452 KB wrong parameter
17 Incorrect 34 ms 6412 KB wrong parameter
18 Incorrect 43 ms 6676 KB wrong parameter
19 Incorrect 32 ms 6276 KB wrong parameter
20 Incorrect 69 ms 6960 KB wrong parameter
21 Incorrect 92 ms 7016 KB wrong parameter
22 Incorrect 45 ms 6536 KB wrong parameter
23 Incorrect 65 ms 7220 KB wrong parameter