Submission #697033

#	Time	Username	Problem	Language	Result	Execution time	Memory
697033		minhcool	City (JOI17_city)	C++17	0 / 100	159 ms	32584 KiB

Encoder

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

#define ll long long
#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 7e5 + 5;
const int mod = 1e9 + 7, oo = 1e18 + 7;

vector<int> Adj[N];

int sz[N], l[N], cnt;

double ind = 1.05;

double arr[N];

int cod[N];

void prep(){
    arr[0] = 1;
    for(int i = 1; ; i++){
        arr[i] = (arr[i - 1] * ind);
        //if(i <= 10) cout << i << " " << arr[i] << '\n';
        if(arr[i] >= 700000) break;
    }
}

void dfs(int u, int p){
    cnt++;
    l[u] = cnt;
    sz[u] = 1;
    for(auto v : Adj[u]){
        if(v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

void dfs2(int u, int p){
    for(auto v : Adj[u]){
        if(v == p) continue;
        dfs2(v, u);
    }
    int total = 1;
    for(auto v : Adj[u]){
        if(v != p){
            total += ceil(arr[cod[v]]);
            //cout << v << " " << cod[v] << " " << total << "\n";
        }
    }
    //cout << u << " " << total << "\n";
    while(arr[cod[u]] < total) cod[u]++;
    //cout << cod[u] << "\n";
}

void Encode(int n, int a[], int b[]){
    prep();
    for(int i = 0; i < (n - 1); i++){
        Adj[a[i]].pb(b[i]);
        Adj[b[i]].pb(a[i]);
    }
    dfs(0, 0);
    dfs2(0, 0);
    //for(int i = 0; i < n; i++) cout << cod[i] << " " << l[i] << "\n";
    for(int i = 0; i < n; i++) Code(i, (ll)cod[i] * (ll)250005 + (ll)l[i]);
}

/*

void process(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i
}

signed main(){
    ios_base::sync_with_stdio(0);
    freopen("KEK.inp", "r", stdin);
    freopen("KEK.out", "w", stdout);
    cin.tie(0);
    process();
}*/

Device

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

#define ll long long
#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;
const int mod = 1e9 + 7, oo = 1e18 + 7;

double _ind = 1.05;

double _arr[N];

void _prep(){
    _arr[0] = 1;
    for(int i = 1; ; i++){
        _arr[i] = (_arr[i - 1] * _ind);
        if(_arr[i] >= 700000) break;
    }
}

void InitDevice(){
    _prep();
}

int Answer(ll x, ll y){
    ll a = x % 250005, b = y % 250005, c = _arr[x / 250005] + a, d = _arr[y / 250005] + b;
    if(a <= b && c >= d) return 1;
    else if(a >= b && c <= d) return 0;
    else return 2;
}

//int n, a[N];

/*

void process(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i
}

signed main(){
    ios_base::sync_with_stdio(0);
    freopen("KEK.inp", "r", stdin);
    freopen("KEK.out", "w", stdout);
    cin.tie(0);
    process();
}*/

Compilation message (stderr)

Encoder.cpp:15:36: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   15 | const int mod = 1e9 + 7, oo = 1e18 + 7;
      |                               ~~~~~^~~

Device.cpp:15:36: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   15 | const int mod = 1e9 + 7, oo = 1e18 + 7;
      |                               ~~~~~^~~

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