#include <bits/stdc++.h>
#include "incursion.h"
//#include "sample_grader.cpp"
using namespace std;
vector<int> mark(vector<pair<int, int>> F, int safe) {
--safe;
int n = F.size() + 1;
vector<vector<int>> adj(n);
for (auto [u, v] : F) {
--u, --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> sz(n, 1), t(n);
function<void(int, int)> dfs = [&](int u, int p) {
for (auto v : adj[u]) {
if (v == p) {
continue;
}
dfs(v, u);
sz[u] += sz[v];
}
if (u != safe && n - sz[u] >= (n + 1) / 2) {
t[u] = 1;
}
};
dfs(safe, -1);
return t;
}
void locate(vector<pair<int, int>> F, int curr, int t) {
--curr;
int n = F.size() + 1;
vector<vector<int>> adj(n);
for (auto [u, v] : F) {
--u, --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> sz(n, 1), par(n, -1);
function<void(int, int)> calc = [&](int u, int p) {
for (auto v : adj[u]) {
if (v == p) {
continue;
}
calc(v, u);
sz[u] += sz[v];
}
if (n - sz[u] == (n + 1) / 2) {
par[u] = p;
par[p] = u;
} else if (n - sz[u] > (n + 1) / 2) {
par[u] = p;
}
};
calc(0, -1);
fill(sz.begin(), sz.end(), 1);
for (int i = 0; i < n; ++i) {
if (par[i] == -1) {
calc(i, -1);
}
if (par[par[i]] == i) {
calc(i, -1);
sz[par[i]] = n;
break;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < adj[i].size(); ++j) {
int v = adj[i][j];
if (v == par[i]) {
swap(adj[i][j], adj[i].back());
adj[i].pop_back();
break;
}
}
sort(adj[i].begin(), adj[i].end(), [&](int u, int v) {
return sz[u] > sz[v];
});
}
vector<int> cnt(n);
function<void(int)> dfs = [&](int u) {
++cnt[u];
if (t == 1) {
t = visit(par[u] + 1);
dfs(par[u]);
} else {
if (adj[u].size() < cnt[u]) {
return;
}
t = visit(adj[u][cnt[u] - 1] + 1);
dfs(adj[u][cnt[u] - 1]);
}
};
dfs(curr);
}
Compilation message
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (int j = 0; j < adj[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~
incursion.cpp: In lambda function:
incursion.cpp:96:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
96 | if (adj[u].size() < cnt[u]) {
interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
44 | if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
50 | int l = (numbers.size() == N ? N : 0);
| ~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
776 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
14940 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
8092 KB |
Correct |
| 2 |
Incorrect |
80 ms |
8032 KB |
Not correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
776 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
