oj.uz

Submission #577013

# Submission time Handle Problem Language Result Execution time Memory
577013 2022-06-13T21:52:08 Z 2fat2code Saveit (IOI10_saveit) C++17
0 / 100
 369 ms 16208 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1005;

int par[nmax];
vector<int>nod[nmax], nod1[nmax];
vector<int>euler;
bitset<nmax>viz;

void dfs(int s){
    viz[s] = 1;
    euler.push_back(s);
    for(auto it : nod1[s]){
        if(!viz[it]){
            dfs(it);
        }
    }
    euler.push_back(s);
}

void encode(int nv, int nh, int ne, int v1[], int v2[]){
    for(int i=0;i<ne;i++){
        nod[v1[i]].push_back(v2[i]);
        nod[v2[i]].push_back(v1[i]);
    }
    for(int i=0;i<nh;i++){
        euler.clear();
        viz.reset();
        for(int i=0;i<nv;i++) nod1[i].clear();
        queue<int>q;
        q.push(i);
        viz[i] = 1;
        while(q.size()){
            auto it = q.front();
            q.pop();
            for(auto it1 : nod[it]){
                if(!viz[it1]){
                    viz[it1] = 1;
                    nod1[it].push_back(it1);
                    q.push(it1);
                }
            }
        }
        viz.reset();
        dfs(i);
        for(auto it : euler){
            for(int i=0;i<=9;i++){
                if(it & (1 << i)) encode_bit(1);
                else encode_bit(0);
            }
        }
    }
    return;
}

#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;

int nn, hh, dist[nmax], first[nmax], last[nmax];
vector<int>oiler;
vector<pair<int,pair<int,int>>>ans;

void decode(int nv, int nh) {
   nn = nv, hh = nh;
   for(int i=0;i<hh;i++){
        oiler.clear();
        for(int j=1;j<=2*nn;j++){

            int curr = 0;
            for(int t=0;t<=9;t++){
                curr += decode_bit() * (1 << t);
            }
            oiler.push_back(curr);
        }
        vector<int>root;
        for(int j=0;j<nn;j++) dist[j] = 0, first[j] = 0, last[j] = 0;
        for(int j=0;j<(int)oiler.size();j++){
            if(!first[oiler[j]]) first[oiler[j]] = (j + 1);
            else last[oiler[j]] = (j + 1);
        }
        for(int j=0;j<(int)oiler.size();j++){
            if(first[oiler[j]] == (j + 1)){
                if(j != 0) dist[oiler[j]] = dist[root.back()] + 1;
                root.push_back(oiler[j]);
            }
            else{
                root.pop_back();
            }
        }
        for(int j=0;j<nn;j++){
            ans.push_back({dist[j], {min(i, j), max(i, j)}});
        }
    }
    sort(all(ans));
    ans.resize(unique(all(ans)) - ans.begin());
    for(auto it : ans){
        hops(it.sc.fr, it.sc.sc, it.fr);
    }
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 369 ms 16208 KB function hops(h,c,d) must be called exactly N×H times
2 Incorrect 1 ms 4612 KB function hops(h,c,d) must be called exactly N×H times
3 Incorrect 125 ms 10436 KB function hops(h,c,d) must be called exactly N×H times
4 Incorrect 3 ms 4612 KB function hops(h,c,d) must be called exactly N×H times
5 Incorrect 116 ms 10616 KB function hops(h,c,d) must be called exactly N×H times
6 Incorrect 142 ms 11548 KB function hops(h,c,d) must be called exactly N×H times
7 Incorrect 155 ms 12060 KB function hops(h,c,d) must be called exactly N×H times
8 Incorrect 126 ms 11068 KB function hops(h,c,d) must be called exactly N×H times
9 Incorrect 149 ms 11364 KB function hops(h,c,d) must be called exactly N×H times
10 Incorrect 139 ms 11472 KB function hops(h,c,d) must be called exactly N×H times
11 Incorrect 135 ms 11608 KB function hops(h,c,d) must be called exactly N×H times
12 Incorrect 138 ms 11324 KB function hops(h,c,d) must be called exactly N×H times
13 Incorrect 162 ms 12028 KB function hops(h,c,d) must be called exactly N×H times
14 Incorrect 146 ms 11408 KB function hops(h,c,d) must be called exactly N×H times
15 Incorrect 134 ms 11504 KB function hops(h,c,d) must be called exactly N×H times
16 Incorrect 159 ms 11984 KB function hops(h,c,d) must be called exactly N×H times
17 Incorrect 154 ms 11892 KB function hops(h,c,d) must be called exactly N×H times
18 Incorrect 152 ms 12148 KB function hops(h,c,d) must be called exactly N×H times
19 Incorrect 140 ms 11748 KB function hops(h,c,d) must be called exactly N×H times
20 Incorrect 168 ms 12356 KB function hops(h,c,d) must be called exactly N×H times
21 Incorrect 197 ms 12496 KB function hops(h,c,d) must be called exactly N×H times
22 Incorrect 157 ms 12156 KB function hops(h,c,d) must be called exactly N×H times
23 Incorrect 196 ms 12744 KB function hops(h,c,d) must be called exactly N×H times

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 369 ms 16208 KB function hops(h,c,d) must be called exactly N×H times
2 Incorrect 1 ms 4612 KB function hops(h,c,d) must be called exactly N×H times
3 Incorrect 125 ms 10436 KB function hops(h,c,d) must be called exactly N×H times
4 Incorrect 3 ms 4612 KB function hops(h,c,d) must be called exactly N×H times
5 Incorrect 116 ms 10616 KB function hops(h,c,d) must be called exactly N×H times
6 Incorrect 142 ms 11548 KB function hops(h,c,d) must be called exactly N×H times
7 Incorrect 155 ms 12060 KB function hops(h,c,d) must be called exactly N×H times
8 Incorrect 126 ms 11068 KB function hops(h,c,d) must be called exactly N×H times
9 Incorrect 149 ms 11364 KB function hops(h,c,d) must be called exactly N×H times
10 Incorrect 139 ms 11472 KB function hops(h,c,d) must be called exactly N×H times
11 Incorrect 135 ms 11608 KB function hops(h,c,d) must be called exactly N×H times
12 Incorrect 138 ms 11324 KB function hops(h,c,d) must be called exactly N×H times
13 Incorrect 162 ms 12028 KB function hops(h,c,d) must be called exactly N×H times
14 Incorrect 146 ms 11408 KB function hops(h,c,d) must be called exactly N×H times
15 Incorrect 134 ms 11504 KB function hops(h,c,d) must be called exactly N×H times
16 Incorrect 159 ms 11984 KB function hops(h,c,d) must be called exactly N×H times
17 Incorrect 154 ms 11892 KB function hops(h,c,d) must be called exactly N×H times
18 Incorrect 152 ms 12148 KB function hops(h,c,d) must be called exactly N×H times
19 Incorrect 140 ms 11748 KB function hops(h,c,d) must be called exactly N×H times
20 Incorrect 168 ms 12356 KB function hops(h,c,d) must be called exactly N×H times
21 Incorrect 197 ms 12496 KB function hops(h,c,d) must be called exactly N×H times
22 Incorrect 157 ms 12156 KB function hops(h,c,d) must be called exactly N×H times
23 Incorrect 196 ms 12744 KB function hops(h,c,d) must be called exactly N×H times

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 369 ms 16208 KB function hops(h,c,d) must be called exactly N×H times
2 Incorrect 1 ms 4612 KB function hops(h,c,d) must be called exactly N×H times
3 Incorrect 125 ms 10436 KB function hops(h,c,d) must be called exactly N×H times
4 Incorrect 3 ms 4612 KB function hops(h,c,d) must be called exactly N×H times
5 Incorrect 116 ms 10616 KB function hops(h,c,d) must be called exactly N×H times
6 Incorrect 142 ms 11548 KB function hops(h,c,d) must be called exactly N×H times
7 Incorrect 155 ms 12060 KB function hops(h,c,d) must be called exactly N×H times
8 Incorrect 126 ms 11068 KB function hops(h,c,d) must be called exactly N×H times
9 Incorrect 149 ms 11364 KB function hops(h,c,d) must be called exactly N×H times
10 Incorrect 139 ms 11472 KB function hops(h,c,d) must be called exactly N×H times
11 Incorrect 135 ms 11608 KB function hops(h,c,d) must be called exactly N×H times
12 Incorrect 138 ms 11324 KB function hops(h,c,d) must be called exactly N×H times
13 Incorrect 162 ms 12028 KB function hops(h,c,d) must be called exactly N×H times
14 Incorrect 146 ms 11408 KB function hops(h,c,d) must be called exactly N×H times
15 Incorrect 134 ms 11504 KB function hops(h,c,d) must be called exactly N×H times
16 Incorrect 159 ms 11984 KB function hops(h,c,d) must be called exactly N×H times
17 Incorrect 154 ms 11892 KB function hops(h,c,d) must be called exactly N×H times
18 Incorrect 152 ms 12148 KB function hops(h,c,d) must be called exactly N×H times
19 Incorrect 140 ms 11748 KB function hops(h,c,d) must be called exactly N×H times
20 Incorrect 168 ms 12356 KB function hops(h,c,d) must be called exactly N×H times
21 Incorrect 197 ms 12496 KB function hops(h,c,d) must be called exactly N×H times
22 Incorrect 157 ms 12156 KB function hops(h,c,d) must be called exactly N×H times
23 Incorrect 196 ms 12744 KB function hops(h,c,d) must be called exactly N×H times

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 369 ms 16208 KB function hops(h,c,d) must be called exactly N×H times
2 Incorrect 1 ms 4612 KB function hops(h,c,d) must be called exactly N×H times
3 Incorrect 125 ms 10436 KB function hops(h,c,d) must be called exactly N×H times
4 Incorrect 3 ms 4612 KB function hops(h,c,d) must be called exactly N×H times
5 Incorrect 116 ms 10616 KB function hops(h,c,d) must be called exactly N×H times
6 Incorrect 142 ms 11548 KB function hops(h,c,d) must be called exactly N×H times
7 Incorrect 155 ms 12060 KB function hops(h,c,d) must be called exactly N×H times
8 Incorrect 126 ms 11068 KB function hops(h,c,d) must be called exactly N×H times
9 Incorrect 149 ms 11364 KB function hops(h,c,d) must be called exactly N×H times
10 Incorrect 139 ms 11472 KB function hops(h,c,d) must be called exactly N×H times
11 Incorrect 135 ms 11608 KB function hops(h,c,d) must be called exactly N×H times
12 Incorrect 138 ms 11324 KB function hops(h,c,d) must be called exactly N×H times
13 Incorrect 162 ms 12028 KB function hops(h,c,d) must be called exactly N×H times
14 Incorrect 146 ms 11408 KB function hops(h,c,d) must be called exactly N×H times
15 Incorrect 134 ms 11504 KB function hops(h,c,d) must be called exactly N×H times
16 Incorrect 159 ms 11984 KB function hops(h,c,d) must be called exactly N×H times
17 Incorrect 154 ms 11892 KB function hops(h,c,d) must be called exactly N×H times
18 Incorrect 152 ms 12148 KB function hops(h,c,d) must be called exactly N×H times
19 Incorrect 140 ms 11748 KB function hops(h,c,d) must be called exactly N×H times
20 Incorrect 168 ms 12356 KB function hops(h,c,d) must be called exactly N×H times
21 Incorrect 197 ms 12496 KB function hops(h,c,d) must be called exactly N×H times
22 Incorrect 157 ms 12156 KB function hops(h,c,d) must be called exactly N×H times
23 Incorrect 196 ms 12744 KB function hops(h,c,d) must be called exactly N×H times