oj.uz

Submission #427003

# Submission time Handle Problem Language Result Execution time Memory
427003 2021-06-14T11:44:25 Z tqbfjotld City (JOI17_city) C++14
22 / 100
 929 ms 65268 KB 
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;

int lch[500005];
int rch[500005];
int curnodes,n;
vector<int> adjl[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()>2){
        auto i1 = *stuff.begin();
        stuff.erase(stuff.begin());
        auto i2 = *stuff.begin();
        stuff.erase(stuff.begin());
        int nw = curnodes++;
        lch[nw] = i1.second;
        rch[nw] = i2.second;
        stuff.insert({i2.first+1,nw});
    }
    if (stuff.size()==2){
        auto i1 = *stuff.begin();
        stuff.erase(stuff.begin());
        auto i2 = *stuff.begin();
        stuff.erase(stuff.begin());
        lch[node] = i1.second;
        rch[node] = i2.second;
        return i2.first+1;
    }
    if (stuff.size()==1){
        auto i1 = *stuff.begin();
        lch[node] = i1.second;
        return i1.first+1;
    }
    return 0;
}

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+(1LL<<pos));
    }
    if (lch[node]!=-1){
        dfs2(lch[node],curamt,pos+1);
    }
    if (rch[node]!=-1){
        dfs2(rch[node],curamt+(1LL<<pos),pos+1);
    }
}

void Encode(int N, int A[], int B[])
{
    n = N;
    memset(lch,-1,sizeof(lch));
    memset(rch,-1,sizeof(rch));
    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;

void InitDevice()
{
}

int Answer(long long S, long long T)
{
    string s1,s2;
    for (int x = 0; x<64; x++){
        if (S)s1.push_back((S&1)?'1':'0');
        S>>=1;
        if (T)s2.push_back((T&1)?'1':'0');
        T>>=1;
    }
    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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10372 KB Output is correct
2 Correct 7 ms 10372 KB Output is correct
3 Correct 8 ms 10328 KB Output is correct
4 Correct 7 ms 10384 KB Output is correct
5 Correct 7 ms 10384 KB Output is correct
6 Correct 8 ms 10312 KB Output is correct
7 Correct 7 ms 10348 KB Output is correct
8 Correct 6 ms 10344 KB Output is correct
9 Correct 7 ms 10372 KB Output is correct
10 Correct 6 ms 10372 KB Output is correct
11 Correct 6 ms 10372 KB Output is correct
12 Correct 8 ms 10372 KB Output is correct

Subtask #2
14.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 24700 KB Output is correct - L = 16383
2 Correct 294 ms 24744 KB Output is correct - L = 114431
3 Correct 307 ms 24740 KB Output is correct - L = 16383
4 Correct 273 ms 24852 KB Output is correct - L = 1023
5 Correct 682 ms 53060 KB Output is correct - L = 134217578
6 Correct 672 ms 52668 KB Output is correct - L = 134217727
7 Correct 721 ms 52552 KB Output is correct - L = 134217663
8 Correct 763 ms 52344 KB Output is correct - L = 262143
9 Partially correct 831 ms 64184 KB Output is partially correct - L = 68719476735
10 Partially correct 838 ms 65024 KB Output is partially correct - L = 68719476733
11 Partially correct 929 ms 65268 KB Output is partially correct - L = 68719476223
12 Partially correct 893 ms 65180 KB Output is partially correct - L = 68719473471
13 Partially correct 840 ms 58944 KB Output is partially correct - L = 34359738367
14 Partially correct 730 ms 55080 KB Output is partially correct - L = 17179869183
15 Correct 266 ms 24864 KB Output is correct - L = 32767
16 Correct 276 ms 24924 KB Output is correct - L = 131071
17 Correct 264 ms 24968 KB Output is correct - L = 32255
18 Partially correct 754 ms 58316 KB Output is partially correct - L = 34359400255
19 Partially correct 777 ms 58732 KB Output is partially correct - L = 34358108160
20 Partially correct 729 ms 58444 KB Output is partially correct - L = 34294005760
21 Partially correct 736 ms 56760 KB Output is partially correct - L = 34359672831
22 Partially correct 820 ms 57492 KB Output is partially correct - L = 34358460416
23 Partially correct 706 ms 55308 KB Output is partially correct - L = 34358460416
24 Partially correct 694 ms 56420 KB Output is partially correct - L = 17175969792
25 Partially correct 696 ms 54416 KB Output is partially correct - L = 17172496384
26 Partially correct 669 ms 54444 KB Output is partially correct - L = 8588656640
27 Partially correct 675 ms 54232 KB Output is partially correct - L = 4292378624