oj.uz

Submission #578016

# Submission time Handle Problem Language Result Execution time Memory
578016 2022-06-15T18:53:48 Z 2fat2code Saveit (IOI10_saveit) C++17
0 / 100
 294 ms 10712 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+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]);
        }
    }

}

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 Correct 294 ms 10712 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 60 call(s) of encode_bit()
3 Incorrect 23 ms 5864 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 23 ms 5976 KB wrong parameter
6 Incorrect 26 ms 6120 KB wrong parameter
7 Incorrect 45 ms 6380 KB wrong parameter
8 Incorrect 22 ms 5832 KB wrong parameter
9 Incorrect 23 ms 6036 KB wrong parameter
10 Incorrect 20 ms 6032 KB wrong parameter
11 Incorrect 31 ms 6024 KB wrong parameter
12 Incorrect 23 ms 6020 KB wrong parameter
13 Incorrect 40 ms 6636 KB wrong parameter
14 Incorrect 23 ms 6012 KB wrong parameter
15 Incorrect 22 ms 6044 KB wrong parameter
16 Incorrect 59 ms 6348 KB wrong parameter
17 Incorrect 46 ms 6376 KB wrong parameter
18 Incorrect 52 ms 6676 KB wrong parameter
19 Incorrect 40 ms 6368 KB wrong parameter
20 Incorrect 71 ms 6940 KB wrong parameter
21 Incorrect 71 ms 7032 KB wrong parameter
22 Incorrect 40 ms 6668 KB wrong parameter
23 Incorrect 65 ms 7320 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 10712 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 60 call(s) of encode_bit()
3 Incorrect 23 ms 5864 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 23 ms 5976 KB wrong parameter
6 Incorrect 26 ms 6120 KB wrong parameter
7 Incorrect 45 ms 6380 KB wrong parameter
8 Incorrect 22 ms 5832 KB wrong parameter
9 Incorrect 23 ms 6036 KB wrong parameter
10 Incorrect 20 ms 6032 KB wrong parameter
11 Incorrect 31 ms 6024 KB wrong parameter
12 Incorrect 23 ms 6020 KB wrong parameter
13 Incorrect 40 ms 6636 KB wrong parameter
14 Incorrect 23 ms 6012 KB wrong parameter
15 Incorrect 22 ms 6044 KB wrong parameter
16 Incorrect 59 ms 6348 KB wrong parameter
17 Incorrect 46 ms 6376 KB wrong parameter
18 Incorrect 52 ms 6676 KB wrong parameter
19 Incorrect 40 ms 6368 KB wrong parameter
20 Incorrect 71 ms 6940 KB wrong parameter
21 Incorrect 71 ms 7032 KB wrong parameter
22 Incorrect 40 ms 6668 KB wrong parameter
23 Incorrect 65 ms 7320 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 10712 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 60 call(s) of encode_bit()
3 Incorrect 23 ms 5864 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 23 ms 5976 KB wrong parameter
6 Incorrect 26 ms 6120 KB wrong parameter
7 Incorrect 45 ms 6380 KB wrong parameter
8 Incorrect 22 ms 5832 KB wrong parameter
9 Incorrect 23 ms 6036 KB wrong parameter
10 Incorrect 20 ms 6032 KB wrong parameter
11 Incorrect 31 ms 6024 KB wrong parameter
12 Incorrect 23 ms 6020 KB wrong parameter
13 Incorrect 40 ms 6636 KB wrong parameter
14 Incorrect 23 ms 6012 KB wrong parameter
15 Incorrect 22 ms 6044 KB wrong parameter
16 Incorrect 59 ms 6348 KB wrong parameter
17 Incorrect 46 ms 6376 KB wrong parameter
18 Incorrect 52 ms 6676 KB wrong parameter
19 Incorrect 40 ms 6368 KB wrong parameter
20 Incorrect 71 ms 6940 KB wrong parameter
21 Incorrect 71 ms 7032 KB wrong parameter
22 Incorrect 40 ms 6668 KB wrong parameter
23 Incorrect 65 ms 7320 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 10712 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 60 call(s) of encode_bit()
3 Incorrect 23 ms 5864 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 23 ms 5976 KB wrong parameter
6 Incorrect 26 ms 6120 KB wrong parameter
7 Incorrect 45 ms 6380 KB wrong parameter
8 Incorrect 22 ms 5832 KB wrong parameter
9 Incorrect 23 ms 6036 KB wrong parameter
10 Incorrect 20 ms 6032 KB wrong parameter
11 Incorrect 31 ms 6024 KB wrong parameter
12 Incorrect 23 ms 6020 KB wrong parameter
13 Incorrect 40 ms 6636 KB wrong parameter
14 Incorrect 23 ms 6012 KB wrong parameter
15 Incorrect 22 ms 6044 KB wrong parameter
16 Incorrect 59 ms 6348 KB wrong parameter
17 Incorrect 46 ms 6376 KB wrong parameter
18 Incorrect 52 ms 6676 KB wrong parameter
19 Incorrect 40 ms 6368 KB wrong parameter
20 Incorrect 71 ms 6940 KB wrong parameter
21 Incorrect 71 ms 7032 KB wrong parameter
22 Incorrect 40 ms 6668 KB wrong parameter
23 Incorrect 65 ms 7320 KB wrong parameter