oj.uz

Submission #578015

# Submission time Handle Problem Language Result Execution time Memory
578015 2022-06-15T18:52:21 Z 2fat2code Saveit (IOI10_saveit) C++17
0 / 100
 277 ms 10788 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++] + 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 == 1) dust[j+2][it] = dust[j+1][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+1][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]);
        }
    }

}

Compilation message

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:51:103: 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:103: warning: operation on 'curr' may be undefined [-Wsequence-point]
decoder.cpp:51:103: warning: operation on 'curr' may be undefined [-Wsequence-point]
decoder.cpp:51:103: warning: operation on 'curr' may be undefined [-Wsequence-point]

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 277 ms 10788 KB Output isn't correct
2 Correct 2 ms 4612 KB Output is correct - 60 call(s) of encode_bit()
3 Incorrect 20 ms 5736 KB wrong parameter
4 Correct 2 ms 4608 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 22 ms 6088 KB wrong parameter
6 Incorrect 26 ms 6164 KB wrong parameter
7 Incorrect 47 ms 6384 KB wrong parameter
8 Incorrect 21 ms 5864 KB wrong parameter
9 Incorrect 20 ms 6012 KB wrong parameter
10 Incorrect 20 ms 6004 KB wrong parameter
11 Incorrect 27 ms 6176 KB wrong parameter
12 Incorrect 20 ms 5884 KB wrong parameter
13 Incorrect 59 ms 6552 KB wrong parameter
14 Incorrect 20 ms 6020 KB wrong parameter
15 Incorrect 20 ms 5992 KB wrong parameter
16 Incorrect 40 ms 6468 KB wrong parameter
17 Incorrect 47 ms 6396 KB wrong parameter
18 Incorrect 47 ms 6644 KB wrong parameter
19 Incorrect 29 ms 6304 KB wrong parameter
20 Incorrect 55 ms 6932 KB wrong parameter
21 Incorrect 88 ms 6928 KB wrong parameter
22 Incorrect 42 ms 6584 KB wrong parameter
23 Incorrect 62 ms 7300 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 277 ms 10788 KB Output isn't correct
2 Correct 2 ms 4612 KB Output is correct - 60 call(s) of encode_bit()
3 Incorrect 20 ms 5736 KB wrong parameter
4 Correct 2 ms 4608 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 22 ms 6088 KB wrong parameter
6 Incorrect 26 ms 6164 KB wrong parameter
7 Incorrect 47 ms 6384 KB wrong parameter
8 Incorrect 21 ms 5864 KB wrong parameter
9 Incorrect 20 ms 6012 KB wrong parameter
10 Incorrect 20 ms 6004 KB wrong parameter
11 Incorrect 27 ms 6176 KB wrong parameter
12 Incorrect 20 ms 5884 KB wrong parameter
13 Incorrect 59 ms 6552 KB wrong parameter
14 Incorrect 20 ms 6020 KB wrong parameter
15 Incorrect 20 ms 5992 KB wrong parameter
16 Incorrect 40 ms 6468 KB wrong parameter
17 Incorrect 47 ms 6396 KB wrong parameter
18 Incorrect 47 ms 6644 KB wrong parameter
19 Incorrect 29 ms 6304 KB wrong parameter
20 Incorrect 55 ms 6932 KB wrong parameter
21 Incorrect 88 ms 6928 KB wrong parameter
22 Incorrect 42 ms 6584 KB wrong parameter
23 Incorrect 62 ms 7300 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 277 ms 10788 KB Output isn't correct
2 Correct 2 ms 4612 KB Output is correct - 60 call(s) of encode_bit()
3 Incorrect 20 ms 5736 KB wrong parameter
4 Correct 2 ms 4608 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 22 ms 6088 KB wrong parameter
6 Incorrect 26 ms 6164 KB wrong parameter
7 Incorrect 47 ms 6384 KB wrong parameter
8 Incorrect 21 ms 5864 KB wrong parameter
9 Incorrect 20 ms 6012 KB wrong parameter
10 Incorrect 20 ms 6004 KB wrong parameter
11 Incorrect 27 ms 6176 KB wrong parameter
12 Incorrect 20 ms 5884 KB wrong parameter
13 Incorrect 59 ms 6552 KB wrong parameter
14 Incorrect 20 ms 6020 KB wrong parameter
15 Incorrect 20 ms 5992 KB wrong parameter
16 Incorrect 40 ms 6468 KB wrong parameter
17 Incorrect 47 ms 6396 KB wrong parameter
18 Incorrect 47 ms 6644 KB wrong parameter
19 Incorrect 29 ms 6304 KB wrong parameter
20 Incorrect 55 ms 6932 KB wrong parameter
21 Incorrect 88 ms 6928 KB wrong parameter
22 Incorrect 42 ms 6584 KB wrong parameter
23 Incorrect 62 ms 7300 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 277 ms 10788 KB Output isn't correct
2 Correct 2 ms 4612 KB Output is correct - 60 call(s) of encode_bit()
3 Incorrect 20 ms 5736 KB wrong parameter
4 Correct 2 ms 4608 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 22 ms 6088 KB wrong parameter
6 Incorrect 26 ms 6164 KB wrong parameter
7 Incorrect 47 ms 6384 KB wrong parameter
8 Incorrect 21 ms 5864 KB wrong parameter
9 Incorrect 20 ms 6012 KB wrong parameter
10 Incorrect 20 ms 6004 KB wrong parameter
11 Incorrect 27 ms 6176 KB wrong parameter
12 Incorrect 20 ms 5884 KB wrong parameter
13 Incorrect 59 ms 6552 KB wrong parameter
14 Incorrect 20 ms 6020 KB wrong parameter
15 Incorrect 20 ms 5992 KB wrong parameter
16 Incorrect 40 ms 6468 KB wrong parameter
17 Incorrect 47 ms 6396 KB wrong parameter
18 Incorrect 47 ms 6644 KB wrong parameter
19 Incorrect 29 ms 6304 KB wrong parameter
20 Incorrect 55 ms 6932 KB wrong parameter
21 Incorrect 88 ms 6928 KB wrong parameter
22 Incorrect 42 ms 6584 KB wrong parameter
23 Incorrect 62 ms 7300 KB wrong parameter