oj.uz

Submission #578012

# Submission time Handle Problem Language Result Execution time Memory
578012 2022-06-15T18:43:35 Z 2fat2code Saveit (IOI10_saveit) C++17
0 / 100
 204 ms 10780 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 == 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, 0);
        }
    }

}

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 204 ms 10780 KB Output isn't correct
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Incorrect 26 ms 5796 KB Output isn't correct
4 Incorrect 2 ms 4612 KB Output isn't correct
5 Incorrect 23 ms 6084 KB Output isn't correct
6 Incorrect 26 ms 6124 KB Output isn't correct
7 Incorrect 44 ms 6440 KB Output isn't correct
8 Incorrect 20 ms 5796 KB Output isn't correct
9 Incorrect 28 ms 6012 KB Output isn't correct
10 Incorrect 27 ms 6044 KB Output isn't correct
11 Incorrect 31 ms 6044 KB Output isn't correct
12 Incorrect 25 ms 5884 KB Output isn't correct
13 Incorrect 44 ms 6588 KB Output isn't correct
14 Incorrect 24 ms 5968 KB Output isn't correct
15 Incorrect 26 ms 5960 KB Output isn't correct
16 Incorrect 50 ms 6388 KB Output isn't correct
17 Incorrect 61 ms 6316 KB Output isn't correct
18 Incorrect 47 ms 6668 KB Output isn't correct
19 Incorrect 40 ms 6128 KB Output isn't correct
20 Incorrect 59 ms 6952 KB Output isn't correct
21 Incorrect 61 ms 7060 KB Output isn't correct
22 Incorrect 45 ms 6616 KB Output isn't correct
23 Incorrect 65 ms 7248 KB Output isn't correct

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 204 ms 10780 KB Output isn't correct
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Incorrect 26 ms 5796 KB Output isn't correct
4 Incorrect 2 ms 4612 KB Output isn't correct
5 Incorrect 23 ms 6084 KB Output isn't correct
6 Incorrect 26 ms 6124 KB Output isn't correct
7 Incorrect 44 ms 6440 KB Output isn't correct
8 Incorrect 20 ms 5796 KB Output isn't correct
9 Incorrect 28 ms 6012 KB Output isn't correct
10 Incorrect 27 ms 6044 KB Output isn't correct
11 Incorrect 31 ms 6044 KB Output isn't correct
12 Incorrect 25 ms 5884 KB Output isn't correct
13 Incorrect 44 ms 6588 KB Output isn't correct
14 Incorrect 24 ms 5968 KB Output isn't correct
15 Incorrect 26 ms 5960 KB Output isn't correct
16 Incorrect 50 ms 6388 KB Output isn't correct
17 Incorrect 61 ms 6316 KB Output isn't correct
18 Incorrect 47 ms 6668 KB Output isn't correct
19 Incorrect 40 ms 6128 KB Output isn't correct
20 Incorrect 59 ms 6952 KB Output isn't correct
21 Incorrect 61 ms 7060 KB Output isn't correct
22 Incorrect 45 ms 6616 KB Output isn't correct
23 Incorrect 65 ms 7248 KB Output isn't correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 204 ms 10780 KB Output isn't correct
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Incorrect 26 ms 5796 KB Output isn't correct
4 Incorrect 2 ms 4612 KB Output isn't correct
5 Incorrect 23 ms 6084 KB Output isn't correct
6 Incorrect 26 ms 6124 KB Output isn't correct
7 Incorrect 44 ms 6440 KB Output isn't correct
8 Incorrect 20 ms 5796 KB Output isn't correct
9 Incorrect 28 ms 6012 KB Output isn't correct
10 Incorrect 27 ms 6044 KB Output isn't correct
11 Incorrect 31 ms 6044 KB Output isn't correct
12 Incorrect 25 ms 5884 KB Output isn't correct
13 Incorrect 44 ms 6588 KB Output isn't correct
14 Incorrect 24 ms 5968 KB Output isn't correct
15 Incorrect 26 ms 5960 KB Output isn't correct
16 Incorrect 50 ms 6388 KB Output isn't correct
17 Incorrect 61 ms 6316 KB Output isn't correct
18 Incorrect 47 ms 6668 KB Output isn't correct
19 Incorrect 40 ms 6128 KB Output isn't correct
20 Incorrect 59 ms 6952 KB Output isn't correct
21 Incorrect 61 ms 7060 KB Output isn't correct
22 Incorrect 45 ms 6616 KB Output isn't correct
23 Incorrect 65 ms 7248 KB Output isn't correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 204 ms 10780 KB Output isn't correct
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Incorrect 26 ms 5796 KB Output isn't correct
4 Incorrect 2 ms 4612 KB Output isn't correct
5 Incorrect 23 ms 6084 KB Output isn't correct
6 Incorrect 26 ms 6124 KB Output isn't correct
7 Incorrect 44 ms 6440 KB Output isn't correct
8 Incorrect 20 ms 5796 KB Output isn't correct
9 Incorrect 28 ms 6012 KB Output isn't correct
10 Incorrect 27 ms 6044 KB Output isn't correct
11 Incorrect 31 ms 6044 KB Output isn't correct
12 Incorrect 25 ms 5884 KB Output isn't correct
13 Incorrect 44 ms 6588 KB Output isn't correct
14 Incorrect 24 ms 5968 KB Output isn't correct
15 Incorrect 26 ms 5960 KB Output isn't correct
16 Incorrect 50 ms 6388 KB Output isn't correct
17 Incorrect 61 ms 6316 KB Output isn't correct
18 Incorrect 47 ms 6668 KB Output isn't correct
19 Incorrect 40 ms 6128 KB Output isn't correct
20 Incorrect 59 ms 6952 KB Output isn't correct
21 Incorrect 61 ms 7060 KB Output isn't correct
22 Incorrect 45 ms 6616 KB Output isn't correct
23 Incorrect 65 ms 7248 KB Output isn't correct