Submission #699566

# Submission time Handle Problem Language Result Execution time Memory
699566 2023-02-17T12:06:10 Z urosk City (JOI17_city) C++14
8 / 100
393 ms 54048 KB
#include "Encoder.h"
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll int
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
#define maxn 900005
ll n;
vector<ll> g[maxn];
ll in[maxn],ti = 0;
void dfs(ll u,ll p){
    in[u] = ++ti;
    for(ll s : g[u]) if(s^p) dfs(s,u);
    double cur = 1.0,w = 1.05;
    ll ans = 0;
    while((ll)cur<ti-in[u]) cur*=w,ans++;
    ti = in[u] + (ll)(cur);
    Code(u,maxn*ans+in[u]);
}
void Encode(int N, int A[], int B[])
{
	n = N;
	for(ll i = 0;i<n-1;i++){
        ll x = A[i],y = B[i];
        g[x].pb(y);
        g[y].pb(x);
	}
    dfs(0,0);
}
#include "Device.h"
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
#define maxx 3005
#define maxn 900005
ll len[maxx];
void InitDevice()
{
    double cur = 1.0,w =1.05;
    len[0] = cur;
    for(ll i = 1;i<maxx;i++){
        cur*=w;
        len[i] = (ll)(cur);
    }
}

int Answer(ll u,ll v)
{
    ll inu = u%maxn,inv = v%maxn;
    ll outu = inu + len[u/maxn],outv = inv + len[v/maxn];
    if(inv>=inu&&outu>=outv) return 1;
    if(inv<=inu&&outu<=outv) return 0;
	return 2;
}
# Verdict Execution time Memory Grader output
1 Correct 10 ms 21816 KB Output is correct
2 Correct 10 ms 21680 KB Output is correct
3 Correct 10 ms 21816 KB Output is correct
4 Correct 13 ms 21896 KB Output is correct
5 Correct 11 ms 21936 KB Output is correct
6 Correct 13 ms 21808 KB Output is correct
7 Correct 11 ms 21832 KB Output is correct
8 Correct 12 ms 21768 KB Output is correct
9 Correct 10 ms 21944 KB Output is correct
10 Correct 10 ms 21804 KB Output is correct
11 Correct 12 ms 21868 KB Output is correct
12 Correct 10 ms 21808 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 167 ms 30304 KB Output is correct - L = 129600721
2 Correct 167 ms 30280 KB Output is correct - L = 130500726
3 Correct 177 ms 30324 KB Output is correct - L = 130500726
4 Correct 162 ms 30256 KB Output is correct - L = 131400731
5 Correct 393 ms 53464 KB Output is correct - L = 241201341
6 Correct 368 ms 53380 KB Output is correct - L = 241201341
7 Correct 393 ms 53368 KB Output is correct - L = 241201341
8 Correct 378 ms 53124 KB Output is correct - L = 244801361
9 Incorrect 312 ms 54048 KB Wrong Answer [6]
10 Halted 0 ms 0 KB -