#include <vector>
#include "incursion.h"
#include <cstdio>
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;
ll sub[50000];
vector<ll> edges[50000];
ll ancc[50000][30];
ll par[50000];
ll visited[50000];
ll depth[50000];
ll unsure[50000];
ll anc(ll a, ll x){
if (a==1) return 1;
if (x==0) return par[a];
if (ancc[a][x] != -1) return ancc[a][x];
return ancc[a][x] = anc(anc(a,x-1),x-1);
}
ll lca(ll a, ll b){
if (depth[a] < depth[b]) swap(a,b);
FORNEG(i,29,-1) if (depth[anc(a,i)] >= depth[b]) a = anc(a,i);
if (a==b) return a;
FORNEG(i,29,-1) if (anc(a,i) != anc(b,i)) a = anc(a,i), b = anc(b,i);
return par[a];
}
void dfs(ll a, ll p, ll d){
depth[a] = d;
par[a] = p;
sub[a] = 1;
for (auto&i : edges[a]){
if (i != p) dfs(i,a,d+1), sub[a] += sub[i];
}
}
vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
vector<int> ties(F.size()+1);
FOR(i,0,50000) edges[i].clear(), sub[i] = 0, par[i] = -1, depth[i] = 0;
FOR(i,0,50000) FOR(j,0,30) ancc[i][j] = -1;
for (auto&i : F){
edges[i.first].push_back(i.second);
edges[i.second].push_back(i.first);
}
dfs(1, -1, 0);
ll n = F.size()+1;
FOR(i,1,n+1){
if (safe == i){
ties[i-1] = 2;
continue;
}
vector<ll> idk;
for (auto&k : edges[i]){
if (k==par[i])idk.push_back(n-sub[i]);
else idk.push_back(sub[k]);
}
sort(idk.begin(), idk.end());
ll nxt = -1;
ll sz = 0;
for (auto&k : edges[i]){
if (k != par[i] && lca(k, safe) == k) nxt = k;
}
if (nxt==-1) nxt = par[i];
if (nxt == par[i]) sz = n-sub[i];
else sz = sub[nxt];
if (sz == idk[idk.size()-1]){
ties[i-1] = 1;
}else{
ties[i-1] = 0;
}
}
return ties;
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
FOR(i,0,50000) edges[i].clear(), sub[i] = 0, par[i] = -1, depth[i] = 0, visited[i] = 0, unsure[i] = 0;
FOR(i,0,50000) FOR(j,0,30) ancc[i][j] = -1;
for (auto&i : F){
edges[i.first].push_back(i.second);
edges[i.second].push_back(i.first);
}
dfs(1, -1, 0);
ll n = F.size()+1;
ll here = t;
while(here != 2){
cout << curr << endl;
visited[curr] += 1;
vector<vector<ll>> idk;
for (auto&k : edges[curr]){
if (par[curr] == k)idk.push_back({n-sub[curr], par[curr]});
else idk.push_back({sub[k], k});
}
sort(idk.begin(), idk.end());
if (idk.size()==2 && idk[0][0]==idk[1][0]) unsure[curr] = 1;
if (idk.size()==3){
if (here==1 && idk[2][0]==idk[1][0]) unsure[curr] =1;
if (here==0 && idk[2][0]!=idk[1][0]) unsure[curr] = 1;
}
if (idk.size()==3 && idk[0][0]==idk[2][0]) unsure[curr] = 2;
if (here==0){
if (visited[idk[0][1]] && !unsure[idk[0][1]] && unsure[curr]) curr = idk[1][1], here = visit(curr);
else curr = idk[0][1], here = visit(curr);
}else{
if (visited[idk[idk.size()-1][1]] && !unsure[idk[idk.size()-1][1]] && unsure[curr]){
if (visited[idk[idk.size()-2][1]] && !unsure[idk[idk.size()-2][1]] && unsure[curr]==2)curr = idk[idk.size()-3][1], here = visit(curr);
else curr = idk[idk.size()-2][1], here = visit(curr);
}
else{
curr = idk[idk.size()-1][1], here = visit(curr);
}
}
}
return;
}
Compilation message
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 |
3 ms |
30212 KB |
Security violation! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
38248 KB |
Security violation! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
107 ms |
35708 KB |
Partially correct |
| 2 |
Incorrect |
108 ms |
35812 KB |
Security violation! |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
30212 KB |
Security violation! |
| 2 |
Halted |
0 ms |
0 KB |
- |
