Submission #427381

# Submission time Handle Problem Language Result Execution time Memory
427381 2021-06-14T14:43:52 Z tqbfjotld City (JOI17_city) C++14
70 / 100
939 ms 57388 KB
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;

int lch[500005];
int rch[500005];
int curnodes,n;
vector<int> adjl[250005];
double const1 = 0.0;
double const2 = 1.0;
const int cutoffval = 10;

double func(int node, int pa){
    set<pair<double,int> > stuff;
    for (auto x : adjl[node]){
        if (x==pa) continue;
        double res = func(x,node);
        stuff.insert({res,x});
    }
    while (stuff.size()>2){
        auto i1 = *stuff.begin();
        stuff.erase(stuff.begin());
        pair<double,int> thing = {-999.0,-1};
        auto it = stuff.lower_bound({i1.first+const1,-1});
        if (it!=stuff.end()){
            thing = (*it);
        }
        if (it!=stuff.begin()){
             it--;
             if (abs(thing.first-(i1.first+const1))>=abs((*it).first-(i1.first+const1))){
                thing = *it;
             }
        }
        auto i2 = thing;
        stuff.erase(stuff.lower_bound(thing));
        int nw = curnodes++;
        lch[nw] = i2.second;
        rch[nw] = i1.second;
        stuff.insert({max(i2.first+const2,i1.first+const1+const2),nw});
    }
    if (stuff.size()==2){
        auto i1 = *stuff.begin();
        stuff.erase(stuff.begin());
        auto i2 = *stuff.begin();
        stuff.erase(stuff.begin());
        lch[node] = i2.second;
        rch[node] = i1.second;
        return max(i2.first+const2,i1.first+const1+const2);
    }
    if (stuff.size()==1){
        auto i1 = *stuff.begin();
        lch[node] = i1.second;
        return i1.first+const2;
    }
    return 0.0;
}

void dfs2(int node, long long curamt, int pos, int h){
    //printf("ch of %d = %d %d\n",node,lch[node],rch[node]);
    //printf("pos = %d\n",pos);
    if (node<n){
       // printf("code %d %lld\n",node,curamt+(1LL<<pos));
        Code(node,curamt+(1LL<<pos));
    }

    if (h>=cutoffval){
        if (lch[node]!=-1){
            dfs2(lch[node],curamt,pos+1,h+1);
        }
        if (rch[node]!=-1){
            dfs2(rch[node],curamt+(1LL<<pos),pos+1,h+1);
        }
    return;
    }

    if (lch[node]!=-1){
       if (lch[node]<n) Code(lch[node],curamt+(5LL<<pos));
        if (lch[lch[node]]!=-1){
            dfs2(lch[lch[node]],curamt,pos+1,h+2);
        }
        if (rch[lch[node]]!=-1){
            dfs2(rch[lch[node]],curamt+(1LL<<pos),pos+3,h+2);
        }
    }
    if (rch[node]!=-1){
      if (rch[node]<n)  Code(rch[node],curamt+(7LL<<pos));
        if (lch[rch[node]]!=-1){
            dfs2(lch[rch[node]],curamt+(3LL<<pos),pos+3,h+2);
        }
        if (rch[rch[node]]!=-1){
            dfs2(rch[rch[node]],curamt+(7LL<<pos),pos+3,h+2);
        }
    }
}

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,0);
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;

const int cutoffval = 10;

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();
    int h = 0;
    for (int x = 0; x<min(s1.size(),s2.size());){
        if (h>=cutoffval){
            if (s1[x]!=s2[x]) return 2;
            x++;
            continue;
        }
        if (s1[x]=='0'){
            if (s2[x]=='0') {
                x++; h+=2; continue;
            }
            if (s2[x+1]=='0'){
                if (s2.size()==x+2){
                    return 0;
                }
            }
            return 2;
        }
        else if (s2[x]=='0'){
            if (s1[x+1]=='0'){
                if (s1.size()==x+2){
                    return 1;
                }
            }
            return 2;
        }
        else if (min(s1.size(),s2.size())==x+2){
            if (s1[x]==s2[x] && s1[x+1]==s2[x+1]) {
                x+=2;
                h += 1;
                continue;
            }
            else{
                return 2;
            }
        }
        else{
            if (s1[x]==s2[x] && s1[x+1]==s2[x+1] && s1[x+2]==s2[x+2]){
                x+=3;
                h+=2;
                continue;
            }
            return 2;
        }
    }
    //printf("cmp %s %s\n",s1.c_str(),s2.c_str());
    return s1.size()<s2.size()?1:0;
    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:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   23 |     for (int x = 0; x<min(s1.size(),s2.size());){
      |                     ~^~~~~~~~~~~~~~~~~~~~~~~~~
Device.cpp:34:30: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |                 if (s2.size()==x+2){
      |                     ~~~~~~~~~^~~~~
Device.cpp:42:30: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |                 if (s1.size()==x+2){
      |                     ~~~~~~~~~^~~~~
Device.cpp:48:42: warning: comparison of integer expressions of different signedness: 'const long unsigned int' and 'int' [-Wsign-compare]
   48 |         else if (min(s1.size(),s2.size())==x+2){
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
Device.cpp:70:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (int x = 0; x<s1.size(); x++){
      |                         ~^~~~~~~~~~
Device.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int x = 0; x<s2.size(); x++){
      |                     ~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 7 ms 10368 KB Output is correct
2 Correct 7 ms 10380 KB Output is correct
3 Correct 7 ms 10364 KB Output is correct
4 Correct 8 ms 10368 KB Output is correct
5 Correct 7 ms 10368 KB Output is correct
6 Correct 9 ms 10272 KB Output is correct
7 Correct 8 ms 10368 KB Output is correct
8 Correct 8 ms 10424 KB Output is correct
9 Correct 8 ms 10372 KB Output is correct
10 Correct 9 ms 10292 KB Output is correct
11 Correct 7 ms 10352 KB Output is correct
12 Correct 7 ms 10368 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 253 ms 18940 KB Output is correct - L = 226009
2 Correct 264 ms 18892 KB Output is correct - L = 57638
3 Correct 258 ms 18944 KB Output is correct - L = 79579
4 Correct 298 ms 18936 KB Output is correct - L = 32761
5 Partially correct 667 ms 40908 KB Output is partially correct - L = 2031392347
6 Partially correct 694 ms 40912 KB Output is partially correct - L = 1028929483
7 Partially correct 675 ms 41108 KB Output is partially correct - L = 1954558553
8 Correct 672 ms 40860 KB Output is correct - L = 8388607
9 Partially correct 877 ms 55740 KB Output is partially correct - L = 2147475456
10 Partially correct 903 ms 57248 KB Output is partially correct - L = 2147475456
11 Partially correct 939 ms 57320 KB Output is partially correct - L = 2147475456
12 Partially correct 922 ms 57388 KB Output is partially correct - L = 2147475456
13 Partially correct 812 ms 49240 KB Output is partially correct - L = 1073733632
14 Partially correct 677 ms 44344 KB Output is partially correct - L = 536862720
15 Correct 259 ms 18916 KB Output is correct - L = 210649
16 Correct 262 ms 18920 KB Output is correct - L = 332489
17 Correct 260 ms 18812 KB Output is correct - L = 103113
18 Partially correct 743 ms 48760 KB Output is partially correct - L = 1073711104
19 Partially correct 773 ms 49164 KB Output is partially correct - L = 1073489920
20 Partially correct 751 ms 49004 KB Output is partially correct - L = 1072472064
21 Partially correct 705 ms 46420 KB Output is partially correct - L = 1073737728
22 Partially correct 757 ms 47036 KB Output is partially correct - L = 1069586432
23 Partially correct 735 ms 44632 KB Output is partially correct - L = 1069586432
24 Partially correct 752 ms 45836 KB Output is partially correct - L = 535943680
25 Partially correct 712 ms 43492 KB Output is partially correct - L = 536576768
26 Correct 708 ms 43512 KB Output is correct - L = 267426688
27 Correct 682 ms 43188 KB Output is correct - L = 133774304