oj.uz

Submission #426551

# Submission time Handle Problem Language Result Execution time Memory
426551 2021-06-14T06:29:14 Z 반딧불(#7615) City (JOI17_city) C++14
30 / 100
 628 ms 50468 KB 
#include <bits/stdc++.h>
#include "Encoder.h"

using namespace std;

typedef long long ll;

namespace {
    int n;
    vector<int> link[250002];
    int sz[250002];
    ll in[250002], out[250002], 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 5 ms 6404 KB Output is correct
2 Correct 5 ms 6404 KB Output is correct
3 Correct 5 ms 6404 KB Output is correct
4 Correct 4 ms 6404 KB Output is correct
5 Correct 5 ms 6404 KB Output is correct
6 Correct 6 ms 6392 KB Output is correct
7 Correct 4 ms 6404 KB Output is correct
8 Correct 5 ms 6404 KB Output is correct
9 Correct 6 ms 6500 KB Output is correct
10 Correct 6 ms 6412 KB Output is correct
11 Correct 6 ms 6444 KB Output is correct
12 Correct 5 ms 6404 KB Output is correct

Subtask #2
22.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 15056 KB Output is correct - L = 245349
2 Correct 227 ms 14960 KB Output is correct - L = 244649
3 Correct 229 ms 14968 KB Output is correct - L = 245349
4 Correct 270 ms 14992 KB Output is correct - L = 245349
5 Partially correct 589 ms 48504 KB Output is partially correct - L = 31250124999
6 Partially correct 628 ms 49620 KB Output is partially correct - L = 31250124999
7 Partially correct 609 ms 49740 KB Output is partially correct - L = 31250124999
8 Partially correct 626 ms 49488 KB Output is partially correct - L = 31250124999
9 Partially correct 523 ms 50308 KB Output is partially correct - L = 31250124999
10 Partially correct 519 ms 50468 KB Output is partially correct - L = 31250124999
11 Partially correct 508 ms 50408 KB Output is partially correct - L = 31250124999
12 Partially correct 499 ms 50444 KB Output is partially correct - L = 31250124999
13 Partially correct 554 ms 50104 KB Output is partially correct - L = 31250124999
14 Partially correct 568 ms 49840 KB Output is partially correct - L = 31250124999
15 Correct 246 ms 22024 KB Output is correct - L = 245349
16 Correct 235 ms 21876 KB Output is correct - L = 245349
17 Correct 229 ms 22036 KB Output is correct - L = 245349
18 Partially correct 537 ms 49960 KB Output is partially correct - L = 31250124999
19 Partially correct 574 ms 49908 KB Output is partially correct - L = 31250124999
20 Partially correct 566 ms 50056 KB Output is partially correct - L = 31250124999
21 Partially correct 575 ms 49860 KB Output is partially correct - L = 31250124999
22 Partially correct 606 ms 50004 KB Output is partially correct - L = 31250124999
23 Partially correct 592 ms 49776 KB Output is partially correct - L = 31250124999
24 Partially correct 594 ms 49820 KB Output is partially correct - L = 31250124999
25 Partially correct 621 ms 49784 KB Output is partially correct - L = 31250124999
26 Partially correct 622 ms 49708 KB Output is partially correct - L = 31250124999
27 Partially correct 623 ms 49632 KB Output is partially correct - L = 31250124999