oj.uz

답안 #697045

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697045 2023-02-08T02:14:52 Z minhcool City (JOI17_city) C++17
100 / 100
 471 ms 60816 KB 
#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();
}*/
#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

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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 24132 KB Output is correct
2 Correct 11 ms 24132 KB Output is correct
3 Correct 14 ms 24112 KB Output is correct
4 Correct 12 ms 24108 KB Output is correct
5 Correct 12 ms 24100 KB Output is correct
6 Correct 12 ms 24164 KB Output is correct
7 Correct 12 ms 24148 KB Output is correct
8 Correct 11 ms 24140 KB Output is correct
9 Correct 11 ms 24192 KB Output is correct
10 Correct 11 ms 24140 KB Output is correct
11 Correct 12 ms 24208 KB Output is correct
12 Correct 11 ms 24128 KB Output is correct

Subtask #2
92.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 32656 KB Output is correct - L = 74000371
2 Correct 165 ms 32644 KB Output is correct - L = 75000376
3 Correct 159 ms 32744 KB Output is correct - L = 75000376
4 Correct 167 ms 32692 KB Output is correct - L = 75000376
5 Correct 413 ms 58836 KB Output is correct - L = 197000986
6 Correct 402 ms 58684 KB Output is correct - L = 198000991
7 Correct 419 ms 58732 KB Output is correct - L = 198000991
8 Correct 452 ms 58428 KB Output is correct - L = 200001001
9 Correct 327 ms 59228 KB Output is correct - L = 207001036
10 Correct 346 ms 59432 KB Output is correct - L = 209001046
11 Correct 329 ms 58896 KB Output is correct - L = 209001046
12 Correct 329 ms 58540 KB Output is correct - L = 209001046
13 Correct 384 ms 59104 KB Output is correct - L = 202001011
14 Correct 404 ms 58840 KB Output is correct - L = 199000996
15 Correct 159 ms 32740 KB Output is correct - L = 75000376
16 Correct 156 ms 32668 KB Output is correct - L = 75000376
17 Correct 155 ms 32672 KB Output is correct - L = 75000376
18 Correct 395 ms 58908 KB Output is correct - L = 208001041
19 Correct 397 ms 60816 KB Output is correct - L = 208001041
20 Correct 374 ms 60692 KB Output is correct - L = 208001041
21 Correct 429 ms 60764 KB Output is correct - L = 207001036
22 Correct 426 ms 60704 KB Output is correct - L = 207001036
23 Correct 394 ms 60592 KB Output is correct - L = 207001036
24 Correct 419 ms 60596 KB Output is correct - L = 206001031
25 Correct 408 ms 60452 KB Output is correct - L = 205001026
26 Correct 427 ms 60492 KB Output is correct - L = 206001031
27 Correct 471 ms 60428 KB Output is correct - L = 205001026