oj.uz

Submission #426550

# Submission time Handle Problem Language Result Execution time Memory
426550 2021-06-14T06:28:13 Z 반딧불(#7615) City (JOI17_city) C++14
8 / 100
 241 ms 18476 KB 
#include <bits/stdc++.h>
#include "Encoder.h"

using namespace std;

typedef long long ll;

namespace {
    int n;
    vector<int> link[100002];
    int sz[100002];
    ll in[100002], out[100002], inCnt;
}

void dfs_sz(int x, int par = -1){
    if(par != -1){
        link[x].erase(find(link[x].begin(), link[x].end(), par));
    }
    sz[x] = 1;
    out[x] = in[x] = inCnt++;
    for(auto y: link[x]){
        dfs_sz(y, x);
        sz[y] += sz[x];
        out[x] = max(out[x], out[y]);
    }
}

void Encode(int N, int A[], int B[]){
	n = N;
	for(int i=0; i<n-1; i++) link[A[i]].push_back(B[i]);
	for(int i=0; i<n-1; i++) link[B[i]].push_back(A[i]);

	dfs_sz(0);

	for(int i=0; i<n; i++){
//        printf("%d: %lld\n", i, out[i] * (out[i] + 1) / 2 + in[i]);
        Code(i, out[i] * (out[i] + 1) / 2 + in[i]);
	}
}

#include <bits/stdc++.h>
#include "Device.h"

using namespace std;

typedef long long ll;

void InitDevice(){

}

pair<ll, ll> calc(ll x){
    ll L = 0, R = 250000, A = 0;
    while(L<=R){
        ll M = (L+R)/2;
        if(M * (M+1) / 2 > x) R = M-1;
        else L = M+1, A = M;
    }
    return make_pair(x - A * (A+1) / 2, A);
}

int Answer(ll S, ll T){
	pair<ll, ll> s = calc(S);
	pair<ll, ll> t = calc(T);
	if(s < t){
        if(s.second >= t.second) return 1;
        return 2;
	}
	if(s.second <= t.second) return 0;
	return 2;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2936 KB Output is correct
2 Correct 2 ms 2936 KB Output is correct
3 Correct 3 ms 3176 KB Output is correct
4 Correct 2 ms 2968 KB Output is correct
5 Correct 2 ms 2956 KB Output is correct
6 Correct 2 ms 2936 KB Output is correct
7 Correct 2 ms 2960 KB Output is correct
8 Correct 2 ms 2936 KB Output is correct
9 Correct 3 ms 2936 KB Output is correct
10 Correct 4 ms 2924 KB Output is correct
11 Correct 3 ms 2936 KB Output is correct
12 Correct 2 ms 2936 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 18460 KB Output is correct - L = 245349
2 Correct 232 ms 18340 KB Output is correct - L = 244649
3 Correct 241 ms 18392 KB Output is correct - L = 245349
4 Correct 227 ms 18476 KB Output is correct - L = 245349
5 Runtime error 72 ms 16528 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -