QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #399837 | #370. City | bashkort# | Compile Error | / | / | C++20 | 5.2kb | 2024-04-26 18:10:37 | 2024-04-28 06:10:28 |
Judging History
Encoder
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
void Encode(int n, int U[], int V[]) {
vector<vector<int>> adj(n);
for (int i = 0; i < n - 1; ++i) {
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
}
constexpr int B = 100;
constexpr int A0 = 8, A1 = 14;
vector<int> code(n), siz(n), type(n), father(n), tin(n), tout(n);
vector<vector<int>> g(n);
auto dfs = [&](auto self, int v) -> void {
siz[v] = 1;
vector<int> nxt;
for (int to : adj[v]) {
adj[to].erase(std::find(adj[to].begin(), adj[to].end(), v));
self(self, to);
siz[v] += siz[to];
}
type[v] = siz[v] >= B;
for (int to : adj[v]) {
if (siz[to] < B && type[v] == 1) {
nxt.push_back(to);
} else {
g[v].push_back(to);
}
}
if (type[v] == 0) {
return;
}
vector<int> stk;
int sum_stk = 0;
for (int x : nxt) {
stk.push_back(x);
sum_stk += siz[x];
if (sum_stk >= B) {
int new_vertex = size(tin);
g.push_back(stk);
g[v].push_back(new_vertex);
tin.push_back({}), tout.push_back({});
type.push_back(1);
stk.clear();
sum_stk = 0;
}
}
g[v].insert(g[v].end(), stk.begin(), stk.end());
sum_stk = 0;
};
dfs(dfs, 0);
int cnt[2]{};
auto gfs = [&](auto self, int v, int last) -> void {
tin[v] = cnt[type[v]];
cnt[type[v]] += 1;
if (type[v] == 1) {
for (int to : g[v]) {
if (type[to] == 1) {
self(self, to, v);
}
}
cnt[0] = 0;
for (int to : g[v]) {
if (type[to] == 0) {
self(self, to, v);
}
}
} else {
father[v] = last;
for (int to : g[v]) {
self(self, to, last);
}
}
tout[v] = cnt[type[v]];
};
gfs(gfs, 0, 0);
int mx = 0;
for (int i = 0; i < g.size(); ++i) {
if (type[i] == 1) {
mx = max(mx, tout[i]);
}
}
assert((1 << A1) > mx);
for (int v = 0; v < n; ++v) {
if (type[v] == 1) {
code[v] = ((((tout[v] - tin[v]) << A1) + tin[v]) << 1) + 1;
} else {
code[v] = (((((tin[father[v]] << A0) + tout[v] - tin[v]) << A0) + tin[v]) << 1) + 0;
}
// cerr << code[v] << " \n"[v == n - 1];
}
for (int i = 0; i < n; ++i) {
Code(i, code[i]);
}
}
Device
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int B = 100;
constexpr int A0 = 7, A1 = 14;
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int B = 100;
constexpr int A0 = 8, A1 = 14;
array<int, 3> query(long long S) {
if (S % 2 == 0) {
S /= 2;
int tin = S & ((1 << A0) - 1);
int tout = tin + ((S >> A0) & ((1 << A0) - 1));
int father = (S >> (2 * A0));
return {tin, tout, father};
} else {
S /= 2;
int tin = S & ((1 << A1) - 1);
int tout = tin + ((S >> A1) & ((1 << A1) - 1));
return {tin, tout, -1};
}
}
void InitDevice() {
}
int Answer(long long S, long long T) {
auto a = query(S);
auto b = query(T);
if (S % 2 == T % 2) {
if (a[0] <= b[0] && a[1] >= b[1]) {
return 1;
} else if (b[0] <= a[0] && b[1] >= a[1]) {
return 0;
} else {
return 2;
}
} else {
if (S % 2 == 0) {
if (b[0] <= a[2] && b[1] >= a[2]) {
return 0;
} else {
return 2;
}
} else {
if (a[0] <= b[2] && a[1] >= b[2]) {
return 1;
} else {
return 2;
}
}
}
return 0;
}
array<int, 3> query(long long S) {
if (S % 2 == 0) {
S /= 2;
int tin = S & ((1 << A0) - 1);
int tout = tin + ((S >> A0) & ((1 << A0) - 1));
int father = (S >> (2 * A0));
return {tin, tout, father};
} else {
S /= 2;
int tin = S & ((1 << A1) - 1);
int tout = tin + ((S >> A1) & ((1 << A1) - 1));
return {tin, tout, -1};
}
}
void InitDevice() {
}
int Answer(long long S, long long T) {
auto a = query(S);
auto b = query(T);
if (S % 2 == T % 2) {
if (a[0] <= b[0] && a[1] >= b[1]) {
return 1;
} else if (b[0] <= a[0] && b[1] >= a[1]) {
return 0;
} else {
return 2;
}
} else {
if (S % 2 == 0) {
if (b[0] <= a[2] && b[1] >= a[2]) {
return 0;
} else {
return 2;
}
} else {
if (a[0] <= b[2] && a[1] >= b[2]) {
return 1;
} else {
return 2;
}
}
}
return 0;
}
详细
Device.code:13:15: error: redefinition of ‘constexpr const int B’
13 | constexpr int B = 100;
| ^
Device.code:6:15: note: ‘constexpr const int B’ previously defined here
6 | constexpr int B = 100;
| ^
Device.code:14:15: error: redefinition of ‘constexpr const int A0’
14 | constexpr int A0 = 8, A1 = 14;
| ^~
Device.code:7:15: note: ‘constexpr const int A0’ previously defined here
7 | constexpr int A0 = 7, A1 = 14;
| ^~
Device.code:14:23: error: redefinition of ‘constexpr const int A1’
14 | constexpr int A0 = 8, A1 = 14;
| ^~
Device.code:7:23: note: ‘constexpr const int A1’ previously defined here
7 | constexpr int A0 = 7, A1 = 14;
| ^~
Device.code:63:15: error: redefinition of ‘std::array<int, 3> query(long long int)’
63 | array<int, 3> query(long long S) {
| ^~~~~
Device.code:16:15: note: ‘std::array<int, 3> query(long long int)’ previously defined here
16 | array<int, 3> query(long long S) {
| ^~~~~
Device.code:78:6: error: redefinition of ‘void InitDevice()’
78 | void InitDevice() {
| ^~~~~~~~~~
Device.code:31:6: note: ‘void InitDevice()’ previously defined here
31 | void InitDevice() {
| ^~~~~~~~~~
Device.code:81:5: error: redefinition of ‘int Answer(long long int, long long int)’
81 | int Answer(long long S, long long T) {
| ^~~~~~
Device.code:34:5: note: ‘int Answer(long long int, long long int)’ previously defined here
34 | int Answer(long long S, long long T) {
| ^~~~~~
grader.cpp: In function ‘int main(int, char**)’:
grader.cpp:62:34: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=]
62 | printf("%d ", given_code[i]);
| ~^ ~~~~~~~~~~~~~
| | |
| int long long int
| %lld
grader.cpp:73:33: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
73 | scanf("%d", &given_code[i]);
| ~^ ~~~~~~~~~~~~~~
| | |
| | long long int*
| int*
| %lld
grader.cpp:44:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
44 | scanf("%d%d", &N, &Q);
| ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:46:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
46 | scanf("%d%d", &(A[i]), &(B[i]));
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
grader.cpp:49:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
49 | scanf("%d%d", &(X[i]), &(Y[i]));
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
grader.cpp:71:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
71 | scanf("%d%d", &N, &Q);
| ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:73:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
73 | scanf("%d", &given_code[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
grader.cpp:77:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
77 | scanf("%d%d", &X, &Y);
| ~~~~~^~~~~~~~~~~~~~~~