oj.uz

답안 #697041

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697041 2023-02-08T02:06:35 Z minhcool City (JOI17_city) C++17
8 / 100
 411 ms 53468 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)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();
}*/
#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 % 250005, b = y % 250005, c = _arr[x / 250005] + a - 1, d = _arr[y / 250005] + 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 17084 KB Output is correct
2 Correct 9 ms 17084 KB Output is correct
3 Correct 9 ms 17084 KB Output is correct
4 Correct 9 ms 16948 KB Output is correct
5 Correct 9 ms 17076 KB Output is correct
6 Correct 9 ms 17092 KB Output is correct
7 Correct 8 ms 17084 KB Output is correct
8 Correct 8 ms 17084 KB Output is correct
9 Correct 10 ms 17068 KB Output is correct
10 Correct 9 ms 17132 KB Output is correct
11 Correct 8 ms 17084 KB Output is correct
12 Correct 8 ms 17124 KB Output is correct

Subtask #2
0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 157 ms 26240 KB Output is correct - L = 20750416
2 Correct 162 ms 27356 KB Output is correct - L = 21000421
3 Correct 161 ms 27496 KB Output is correct - L = 20750416
4 Correct 163 ms 27436 KB Output is correct - L = 21000421
5 Incorrect 411 ms 53468 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -