Submission #225966

#	Time	Username	Problem	Language	Result	Execution time	Memory
225966		erd1	City (JOI17_city)	C++14	8 / 100	451 ms	16544 KiB

Encoder

#include "Encoder.h"
#include<bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;

template<typename Iter>
ostream& outIt(ostream& out, Iter b, Iter e){
    for(Iter i = b; i != e; i++)
        out << (i == b?"":" ") << *i;
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, vector<T>& v){
    return outIt(out << '[', all(v)) << ']';
}

template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> v){
    return out << "(" << v.first << ", " << v.second << ")";
}

pii operator+(pii a, int b){ return {a.ff+b, a.ss}; }
vector<vector<int>> G;
vector<pii> mxch;

int haash(int i){
    return (i>>10)^(i&1023);
}

long long encode(vector<int> v){
    vector<int> ans;
    reverse(all(v));
    int s = v.size();
    if(!s)return 0;
    //cout << v << " ";
    while(v.size() && !v.back())v.pop_back();
    while(v.size()){
            if(v.back()){v.back() = haash(v.back())?haash(v.back()):1;
                for(int i = __lg(v.back()); i >= 0; i--)ans.pb(v.back()>>i&1);
            }
            ans.pb(2);
            v.pop_back();
        }
    for(int i = __lg(s); i >= 0; i--)ans.pb(s>>i&1);
    //cout << ans << " ";
    long long anss = 0;
    for(auto i: ans)anss = anss*3+i;
    //cout << anss << endl;
    return anss;
}


vector<int> concat(vector<int> v, int i){
    v.pb(i); return v;
}

void dfs(int i, int p, vector<int> v){
    int cnt = 0;
    if(mxch[i].ss)dfs(mxch[i].ss, i, concat(v, cnt++));
    for(auto x: G[i])
        if(x != p && x != mxch[i].ss)
            dfs(x, i, concat(v, cnt++));
    //cout << i << " ";
    Code(i, encode(v));
    //cout << "!" << endl;
}

pii dfs0(int i, int p){
    for(auto x: G[i])if(x != p)dfs0(x, i);
    mxch[p] = max(mxch[i]+1, mxch[p]);
}

void Encode(int N, int A[], int B[]) {
    //cout << "inencode" << endl;
    G.resize(N); mxch.resize(N);
    for(int i = 0; i < N-1; i++)
        G[A[i]].pb(B[i]), G[B[i]].pb(A[i]);
    dfs0(0, 0);
    //cout << "end1" << endl;
    dfs(0, 0, vector<int>());
    //cout << "end2" << endl;
}

Device

#include "Device.h"
#include<bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;

template<typename Iter>
ostream& outIt(ostream& out, Iter b, Iter e){
    for(Iter i = b; i != e; i++)
        out << (i == b?"":" ") << *i;
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, vector<T>& v){
    return outIt(out << '[', all(v)) << ']';
}

template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> v){
    return out << "(" << v.first << ", " << v.second << ")";
}

static pii operator+(pii a, int b){ return {a.ff+b, a.ss}; }

void InitDevice()
{
}

static vector<int> decode(long long c){
    vector<int> v, cs;
    //cout << c << " ";
    while(c)cs.pb(c%3), c/=3;
    reverse(all(cs));
    //cout << cs << " ";
    int cur = 0;
    for(auto i: cs){
        if(i == 2)v.pb(cur), cur = 0;
        else cur = cur*2+i;
    }
    reverse(all(v));
    v.resize(cur, 0);
    reverse(all(v));
    //cout << v << endl;
    return v;
}

int Answer(long long S, long long T) {
    auto s = decode(S), t = decode(T); int a = 1;
    //cout << S << s << endl << T << t << endl;
    if(s.size() > t.size())swap(s, t), a = 1-a;
    for(int i = 0; i < s.size(); i++)if(s[i] != t[i])return 2;
    return a;
}

Compilation message (stderr)

Encoder.cpp: In function 'pii dfs0(int, int)':
Encoder.cpp:76:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Device.cpp: In function 'int Answer(long long int, long long int)':
Device.cpp:55:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < s.size(); i++)if(s[i] != t[i])return 2;
                    ~~^~~~~~~~~~
Device.cpp: At global scope:
Device.cpp:27:12: warning: 'pii operator+(pii, int)' defined but not used [-Wunused-function]
 static pii operator+(pii a, int b){ return {a.ff+b, a.ss}; }
            ^~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 92