Submission #697045

#	Time	Username	Problem	Language	Result	Execution time	Memory
697045		minhcool	City (JOI17_city)	C++17	100 / 100	471 ms	60816 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 = 1e6 + 5;
const int mod = 1e9 + 7, oo = 1e18 + 7;
 
vector<int> Adj[N];
 
int sz[N], l[N], r[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] + 1) * ind);
        //if(i <= 10) cout << i << " " << arr[i] << '\n';
        if(arr[i] >= 1000000) 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];
    }
    r[u] = cnt;
}
 
void dfs2(int u, int p, int x){
    l[u] = x;
    int s = 1;
    for(auto v : Adj[u]){
        if(v == p) continue;
        dfs2(v, u, x + s);
        s += arr[cod[v]];
    }
    assert(s <= 1000000);
    //assert(total <= 100);
    //cout << u << " " << total << "\n";
    while(arr[cod[u]] < (double)s) 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, 1);
    //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)1000005 + (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 = 7e5 + 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] + 1) * _ind);
        if(_arr[i] >= 700000) break;
    }
}
 
void InitDevice(){
    _prep();
}
 
int Answer(ll x, ll y){
    ll a = x % 1000005, b = y % 1000005, c = (ll)_arr[x / 1000005] + a - 1, d = (ll)_arr[y / 1000005] + b - 1;
    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: 8 / 8
• Subtask 2: 92 / 92