oj.uz

답안 #697042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697042 2023-02-08T02:09:24 Z minhcool City (JOI17_city) C++17
8 / 100
 433 ms 54208 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 = 7e5 + 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] >= 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];
    }
    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 += ceil(arr[cod[v]]);
    }
    //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)700005 + (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 % 700005, b = y % 700005, c = _arr[x / 700005] + a - 1, d = _arr[y / 700005] + 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 9 ms 17076 KB Output is correct
2 Correct 9 ms 17088 KB Output is correct
3 Correct 9 ms 17156 KB Output is correct
4 Correct 8 ms 17088 KB Output is correct
5 Correct 11 ms 17060 KB Output is correct
6 Correct 9 ms 17084 KB Output is correct
7 Correct 9 ms 17080 KB Output is correct
8 Correct 9 ms 17088 KB Output is correct
9 Correct 9 ms 17080 KB Output is correct
10 Correct 9 ms 17052 KB Output is correct
11 Correct 9 ms 17080 KB Output is correct
12 Correct 9 ms 17092 KB Output is correct

Subtask #2
0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 25612 KB Output is correct - L = 58100416
2 Correct 155 ms 25612 KB Output is correct - L = 58800421
3 Correct 156 ms 25660 KB Output is correct - L = 58100416
4 Correct 158 ms 25616 KB Output is correct - L = 58800421
5 Correct 433 ms 51696 KB Output is correct - L = 143501026
6 Correct 416 ms 53408 KB Output is correct - L = 144201031
7 Correct 403 ms 53644 KB Output is correct - L = 144201031
8 Correct 423 ms 53200 KB Output is correct - L = 146301046
9 Correct 325 ms 54096 KB Output is correct - L = 144901036
10 Correct 338 ms 54096 KB Output is correct - L = 146301046
11 Correct 326 ms 53580 KB Output is correct - L = 146301046
12 Correct 331 ms 53200 KB Output is correct - L = 146301046
13 Correct 410 ms 54032 KB Output is correct - L = 144201031
14 Correct 416 ms 53512 KB Output is correct - L = 144201031
15 Correct 159 ms 27424 KB Output is correct - L = 58100416
16 Correct 158 ms 27504 KB Output is correct - L = 58800421
17 Correct 160 ms 27724 KB Output is correct - L = 58100416
18 Runtime error 310 ms 54208 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -