#include "Encoder.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define vi vector<int>
#define vl vector<ll>
#define all(a) begin(a),end(a)
using namespace std;
using ll=long long;
const char en='\n';
vi ch[250000];
bool bio[250000];
int cu,ind[250000],r[250000];
void dfs(int i)
{
bio[i]=1;
ind[i]=cu++;
for (auto a: ch[i]) if (!bio[a]) dfs(a);
r[i]=cu;
}
ll to(pair<ll,ll> a)
{
return a.y*(a.y-1)/2+a.x;
}
void Encode(int N, int A[], int B[])
{
for (int i = 0; i < N-1; ++i) {
ch[A[i]].pb(B[i]);
ch[B[i]].pb(A[i]);
}
dfs(0);
for (int i=0;i<N;++i)
{
//cout<<i<<' '<<ind[i]<<' '<<r[i]<<' '<<to({ind[i],r[i]})<<en;
Code(i,to({ind[i],r[i]}));
}
}
#include "Device.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define vi vector<int>
#define vl vector<ll>
#define all(a) begin(a),end(a)
using namespace std;
using ll=long long;
const char en='\n';
void InitDevice()
{
}
pair<ll,ll> from(ll x)
{
ll lo=0,hi=260000;
while (lo<hi)
{
ll mid=(lo+hi+1)/2;
if (x>=mid*(mid-1)/2) lo=mid;
else hi=mid-1;
}
return {x-lo*(lo-1)/2,lo};
}
int Answer(long long S, long long T)
{
auto p1=from(S),p2=from(T);
if (p1.x>=p2.x && p1.x<p2.y)
{
//cout<<S<<' '<<T<<' '<<0<<en;
return 0;
}
if (p2.x>=p1.x && p2.x<p1.y)
{
//cout<<S<<' '<<T<<' '<<1<<en;
return 1;
}
//cout<<S<<' '<<T<<' '<<2<<en;
return 2;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
12544 KB |
Output is correct |
2 |
Correct |
12 ms |
12544 KB |
Output is correct |
3 |
Correct |
12 ms |
12544 KB |
Output is correct |
4 |
Correct |
12 ms |
12544 KB |
Output is correct |
5 |
Correct |
13 ms |
12544 KB |
Output is correct |
6 |
Correct |
11 ms |
12544 KB |
Output is correct |
7 |
Correct |
13 ms |
12544 KB |
Output is correct |
8 |
Correct |
12 ms |
12544 KB |
Output is correct |
9 |
Correct |
12 ms |
12544 KB |
Output is correct |
10 |
Correct |
12 ms |
12544 KB |
Output is correct |
11 |
Correct |
12 ms |
12544 KB |
Output is correct |
12 |
Correct |
12 ms |
12544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
246 ms |
26096 KB |
Output is correct - L = 245349 |
2 |
Correct |
244 ms |
24304 KB |
Output is correct - L = 244649 |
3 |
Correct |
244 ms |
25328 KB |
Output is correct - L = 245349 |
4 |
Correct |
240 ms |
25072 KB |
Output is correct - L = 245349 |
5 |
Partially correct |
562 ms |
66288 KB |
Output is partially correct - L = 31250124999 |
6 |
Partially correct |
555 ms |
68592 KB |
Output is partially correct - L = 31250124999 |
7 |
Partially correct |
567 ms |
69368 KB |
Output is partially correct - L = 31250124999 |
8 |
Partially correct |
565 ms |
67264 KB |
Output is partially correct - L = 31250124999 |
9 |
Partially correct |
502 ms |
70360 KB |
Output is partially correct - L = 31250124999 |
10 |
Partially correct |
492 ms |
71128 KB |
Output is partially correct - L = 31250124999 |
11 |
Partially correct |
487 ms |
71120 KB |
Output is partially correct - L = 31250124999 |
12 |
Partially correct |
530 ms |
71456 KB |
Output is partially correct - L = 31250124999 |
13 |
Partially correct |
552 ms |
69856 KB |
Output is partially correct - L = 31250124999 |
14 |
Partially correct |
559 ms |
69816 KB |
Output is partially correct - L = 31250124999 |
15 |
Correct |
246 ms |
26608 KB |
Output is correct - L = 245349 |
16 |
Correct |
251 ms |
26608 KB |
Output is correct - L = 245349 |
17 |
Correct |
241 ms |
25840 KB |
Output is correct - L = 245349 |
18 |
Partially correct |
534 ms |
69600 KB |
Output is partially correct - L = 31250124999 |
19 |
Partially correct |
530 ms |
69856 KB |
Output is partially correct - L = 31250124999 |
20 |
Partially correct |
531 ms |
69856 KB |
Output is partially correct - L = 31250124999 |
21 |
Partially correct |
540 ms |
70112 KB |
Output is partially correct - L = 31250124999 |
22 |
Partially correct |
546 ms |
69856 KB |
Output is partially correct - L = 31250124999 |
23 |
Partially correct |
535 ms |
69856 KB |
Output is partially correct - L = 31250124999 |
24 |
Partially correct |
544 ms |
69872 KB |
Output is partially correct - L = 31250124999 |
25 |
Partially correct |
552 ms |
70016 KB |
Output is partially correct - L = 31250124999 |
26 |
Partially correct |
571 ms |
70024 KB |
Output is partially correct - L = 31250124999 |
27 |
Partially correct |
563 ms |
68336 KB |
Output is partially correct - L = 31250124999 |