# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
427404 |
2021-06-14T14:57:18 Z |
lyc |
City (JOI17_city) |
C++14 |
|
259 ms |
21712 KB |
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> ii;
const int mxN = 250001;
int N;
vector<int> al[mxN];
int bits[mxN], code[mxN];
void dfs(int u, int p) {
int nc = 0;
for (int& v : al[u]) if (v != p) {
++nc;
}
if (nc > 0) {
--nc;
int shift = 0;
while (nc) shift++, nc >>= 1;
shift = max(shift,1);
int i = 0;
for (int& v : al[u]) if (v != p) {
bits[v] = bits[u] + shift;
code[v] = (code[u]<<shift) | i;
//TRACE(u _ v _ i _ code[v] _ bits[v]);
dfs(v,u);
++i;
}
}
//TRACE(u _ nc _ bits[u] _ code[u]);
}
void Encode(int N, int A[], int B[])
{
FOR(i,0,N-2){
al[A[i]].push_back(B[i]);
al[B[i]].push_back(A[i]);
}
bits[0] = 0, code[0] = 0;
dfs(0,-1);
for (int i = 0; i < N; ++i) {
Code(i, (ll)bits[i] | ((ll)code[i]<<5));
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> ii;
const int MN = 1e6+5;
const int mod = 1e9+7;
void InitDevice()
{
}
int Answer(long long S, long long T)
{
int b1 = S&((1<<5)-1), b2 = T&((1<<5)-1);
if (b1 == b2) return 2;
if (b1 == 0) return 1;
if (b2 == 0) return 0;
S >>= 5;
T >>= 5;
if (b1 < b2) {
if (S == (T>>(b2-b1))) return 1;
return 2;
} else {
if ((S>>(b1-b2)) == T) return 0;
return 2;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
6400 KB |
Output is correct |
2 |
Correct |
4 ms |
6492 KB |
Output is correct |
3 |
Correct |
5 ms |
6408 KB |
Output is correct |
4 |
Correct |
5 ms |
6380 KB |
Output is correct |
5 |
Correct |
4 ms |
6400 KB |
Output is correct |
6 |
Correct |
5 ms |
6492 KB |
Output is correct |
7 |
Correct |
6 ms |
6408 KB |
Output is correct |
8 |
Correct |
6 ms |
6400 KB |
Output is correct |
9 |
Correct |
5 ms |
6456 KB |
Output is correct |
10 |
Correct |
5 ms |
6400 KB |
Output is correct |
11 |
Correct |
4 ms |
6408 KB |
Output is correct |
12 |
Correct |
5 ms |
6404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
222 ms |
16580 KB |
Output is correct - L = 28054166 |
2 |
Partially correct |
201 ms |
16504 KB |
Output is partially correct - L = 6771032670 |
3 |
Correct |
193 ms |
16224 KB |
Output is correct - L = 17633717 |
4 |
Correct |
203 ms |
16212 KB |
Output is correct - L = 8169 |
5 |
Incorrect |
259 ms |
21712 KB |
Wrong Answer [3] |
6 |
Halted |
0 ms |
0 KB |
- |