oj.uz

Submission #427071

# Submission time Handle Problem Language Result Execution time Memory
427071 2021-06-14T12:09:33 Z tqbfjotld City (JOI17_city) C++14
8 / 100
 274 ms 48632 KB 
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> chlist[250005];
int curnodes,n;
vector<int> adjl[250005];
const int numch = 3;
long long expp[250005];

int func(int node, int pa){
    set<pair<int,int> > stuff;
    for (auto x : adjl[node]){
        if (x==pa) continue;
        int res = func(x,node);
        stuff.insert({res,x});
    }
    while (stuff.size()>numch){
        int nw = curnodes++;
        int mxv = -1;
        for (int x = 0; x<numch; x++){
            auto i = *stuff.begin();
            stuff.erase(stuff.begin());
            chlist[nw].push_back(i.second);
            mxv = i.first;
        }
        stuff.insert({mxv+1,nw});
    }
    int mxv = -1;
    for (auto x : stuff){
        mxv = x.first;
        chlist[node].push_back(x.second);
    }
    return mxv+1;
}

void dfs2(int node, long long curamt, int pos){
    //printf("ch of %d = %d %d\n",node,lch[node],rch[node]);
    if (node<n){
       // printf("code %d %lld\n",node,curamt+(1LL<<pos));
        Code(node,curamt+expp[pos]-1LL);
    }
    for (long long x = 0; x<chlist[node].size(); x++){
        dfs2(chlist[node][x],curamt+x*expp[pos],pos+1);
    }
}

void Encode(int N, int A[], int B[])
{
    n = N;
    expp[0] = 1;
    for (int x = 1; x<64; x++){
        expp[x] = expp[x-1]*numch;
    }
    curnodes = N;
    for (int x = 0; x<N-1; x++){
        adjl[A[x]].push_back(B[x]);
        adjl[B[x]].push_back(A[x]);
    }
    func(0,-1);
    dfs2(0,0,0);
}

#include "Device.h"
#include <bits/stdc++.h>
using namespace std;

const int numch = 3;

void InitDevice()
{
}

int Answer(long long S, long long T)
{
    S++; T++;
    string s1,s2;
    for (int x = 0; x<64; x++){
        if (S){
            s1.push_back('0'+S%numch);
        }
        S/=numch;
        if (T){
            s2.push_back('0'+T%numch);
        }
        T/=numch;
    }
    s1.pop_back();
    s2.pop_back();
    //printf("cmp %s %s\n",s1.c_str(),s2.c_str());
    if (s1.size()<s2.size()){
        for (int x = 0; x<s1.size(); x++){
            if (s1[x]!=s2[x]) return 2;
        }
        return 1;
    }
    for (int x = 0; x<s2.size(); x++){
        if (s1[x]!=s2[x]) return 2;
    }
	return 0;
}

Compilation message

Encoder.cpp: In function 'void dfs2(int, long long int, int)':
Encoder.cpp:43:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (long long x = 0; x<chlist[node].size(); x++){
      |                           ~^~~~~~~~~~~~~~~~~~~~

Device.cpp: In function 'int Answer(long long int, long long int)':
Device.cpp:29:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int x = 0; x<s1.size(); x++){
      |                         ~^~~~~~~~~~
Device.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int x = 0; x<s2.size(); x++){
      |                     ~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12296 KB Output is correct
2 Correct 9 ms 12296 KB Output is correct
3 Correct 8 ms 12372 KB Output is correct
4 Correct 7 ms 12292 KB Output is correct
5 Correct 7 ms 12272 KB Output is correct
6 Correct 9 ms 12192 KB Output is correct
7 Correct 8 ms 12380 KB Output is correct
8 Correct 8 ms 12296 KB Output is correct
9 Correct 9 ms 12372 KB Output is correct
10 Correct 8 ms 12296 KB Output is correct
11 Correct 8 ms 12304 KB Output is correct
12 Correct 8 ms 12292 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 21024 KB Output is correct - L = 894704
2 Correct 274 ms 20996 KB Output is correct - L = 43188520
3 Correct 270 ms 20892 KB Output is correct - L = 583836
4 Correct 261 ms 20944 KB Output is correct - L = 29523
5 Runtime error 177 ms 48632 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -