oj.uz

Submission #578006

# Submission time Handle Problem Language Result Execution time Memory
578006 2022-06-15T18:12:30 Z 2fat2code Saveit (IOI10_saveit) C++17
0 / 100
 214 ms 10720 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;
        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 214 ms 10720 KB wrong parameter
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Incorrect 23 ms 5820 KB wrong parameter
4 Incorrect 4 ms 4612 KB Output isn't correct
5 Incorrect 23 ms 6032 KB wrong parameter
6 Incorrect 26 ms 6152 KB wrong parameter
7 Incorrect 37 ms 6488 KB wrong parameter
8 Incorrect 20 ms 5792 KB wrong parameter
9 Incorrect 22 ms 6016 KB wrong parameter
10 Incorrect 25 ms 5940 KB wrong parameter
11 Incorrect 26 ms 6088 KB wrong parameter
12 Incorrect 28 ms 5992 KB wrong parameter
13 Incorrect 51 ms 6576 KB wrong parameter
14 Incorrect 20 ms 6012 KB wrong parameter
15 Incorrect 20 ms 6072 KB wrong parameter
16 Incorrect 41 ms 6372 KB wrong parameter
17 Incorrect 42 ms 6376 KB wrong parameter
18 Incorrect 48 ms 6656 KB wrong parameter
19 Incorrect 36 ms 6300 KB wrong parameter
20 Incorrect 60 ms 6936 KB wrong parameter
21 Incorrect 60 ms 7220 KB wrong parameter
22 Incorrect 42 ms 6592 KB wrong parameter
23 Incorrect 60 ms 7232 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 10720 KB wrong parameter
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Incorrect 23 ms 5820 KB wrong parameter
4 Incorrect 4 ms 4612 KB Output isn't correct
5 Incorrect 23 ms 6032 KB wrong parameter
6 Incorrect 26 ms 6152 KB wrong parameter
7 Incorrect 37 ms 6488 KB wrong parameter
8 Incorrect 20 ms 5792 KB wrong parameter
9 Incorrect 22 ms 6016 KB wrong parameter
10 Incorrect 25 ms 5940 KB wrong parameter
11 Incorrect 26 ms 6088 KB wrong parameter
12 Incorrect 28 ms 5992 KB wrong parameter
13 Incorrect 51 ms 6576 KB wrong parameter
14 Incorrect 20 ms 6012 KB wrong parameter
15 Incorrect 20 ms 6072 KB wrong parameter
16 Incorrect 41 ms 6372 KB wrong parameter
17 Incorrect 42 ms 6376 KB wrong parameter
18 Incorrect 48 ms 6656 KB wrong parameter
19 Incorrect 36 ms 6300 KB wrong parameter
20 Incorrect 60 ms 6936 KB wrong parameter
21 Incorrect 60 ms 7220 KB wrong parameter
22 Incorrect 42 ms 6592 KB wrong parameter
23 Incorrect 60 ms 7232 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 10720 KB wrong parameter
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Incorrect 23 ms 5820 KB wrong parameter
4 Incorrect 4 ms 4612 KB Output isn't correct
5 Incorrect 23 ms 6032 KB wrong parameter
6 Incorrect 26 ms 6152 KB wrong parameter
7 Incorrect 37 ms 6488 KB wrong parameter
8 Incorrect 20 ms 5792 KB wrong parameter
9 Incorrect 22 ms 6016 KB wrong parameter
10 Incorrect 25 ms 5940 KB wrong parameter
11 Incorrect 26 ms 6088 KB wrong parameter
12 Incorrect 28 ms 5992 KB wrong parameter
13 Incorrect 51 ms 6576 KB wrong parameter
14 Incorrect 20 ms 6012 KB wrong parameter
15 Incorrect 20 ms 6072 KB wrong parameter
16 Incorrect 41 ms 6372 KB wrong parameter
17 Incorrect 42 ms 6376 KB wrong parameter
18 Incorrect 48 ms 6656 KB wrong parameter
19 Incorrect 36 ms 6300 KB wrong parameter
20 Incorrect 60 ms 6936 KB wrong parameter
21 Incorrect 60 ms 7220 KB wrong parameter
22 Incorrect 42 ms 6592 KB wrong parameter
23 Incorrect 60 ms 7232 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 10720 KB wrong parameter
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Incorrect 23 ms 5820 KB wrong parameter
4 Incorrect 4 ms 4612 KB Output isn't correct
5 Incorrect 23 ms 6032 KB wrong parameter
6 Incorrect 26 ms 6152 KB wrong parameter
7 Incorrect 37 ms 6488 KB wrong parameter
8 Incorrect 20 ms 5792 KB wrong parameter
9 Incorrect 22 ms 6016 KB wrong parameter
10 Incorrect 25 ms 5940 KB wrong parameter
11 Incorrect 26 ms 6088 KB wrong parameter
12 Incorrect 28 ms 5992 KB wrong parameter
13 Incorrect 51 ms 6576 KB wrong parameter
14 Incorrect 20 ms 6012 KB wrong parameter
15 Incorrect 20 ms 6072 KB wrong parameter
16 Incorrect 41 ms 6372 KB wrong parameter
17 Incorrect 42 ms 6376 KB wrong parameter
18 Incorrect 48 ms 6656 KB wrong parameter
19 Incorrect 36 ms 6300 KB wrong parameter
20 Incorrect 60 ms 6936 KB wrong parameter
21 Incorrect 60 ms 7220 KB wrong parameter
22 Incorrect 42 ms 6592 KB wrong parameter
23 Incorrect 60 ms 7232 KB wrong parameter