# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
426550 |
2021-06-14T06:28:13 Z |
반딧불(#7615) |
City (JOI17_city) |
C++14 |
|
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;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
- |