#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj1;
vector<int> siz;
vector<int> marked;
int n;
void calcsiz(int v, int e){
siz[v]=1;
for(int u: adj1[v]){
if(u==e) continue;
calcsiz(u, v);
siz[v]+=siz[u];
}
return;
}
void dfsmark(int v, int e){
int f1, f2;
f1 = f2 = -1;
for(int u: adj1[v]){
if(u==e) continue;
if(f1!=-1) f2 = u;
else f1 = u;
dfsmark(u, v);
}
int var = n- (f1!=-1 ? siz[f1] : 0) - (f2!=-1 ? siz[f2] : 0)-1;
if(f1!=-1 && siz[f1]>=var){
marked[v]=0;
}
if(f2!=-1 && siz[f2]>=var){
marked[v]=0;
}
return;
}
vector<int> mark(vector<pair<int, int>> F, int safe) {
n = F.size()+1;
safe--;
adj1.resize(n);
/*for(int i = 0; i<n-1; i++){
if(F[i].first == 0 || F[i].second == 0) while(1);
}*/
for(int i = 0; i<n-1; i++){
adj1[F[i].first-1].push_back(F[i].second-1);
adj1[F[i].second-1].push_back(F[i].first-1);
}
siz.resize(n);
calcsiz(safe, safe);
marked.resize(n, 1);
marked[safe]=0;
for(int u: adj1[safe]){
dfsmark(u, safe);
}
while(1);
return marked;
}
vector<vector<pair<int, int>>> adj2;
vector<int> vis;
void calcsiz2(int v, int e){
siz[v]=1;
for(auto eg: adj2[v]){
int u = eg.first;
if(u==e) continue;
calcsiz2(u, v);
siz[v]+=siz[u];
}
return;
}
void calcsiz3(int v, int e){
int var = 0;
for(auto& eg: adj2[v]){
int u = eg.first;
if(u==e){
continue;
}
calcsiz3(u, v);
eg.second = siz[u];
var += siz[u];
}
for(auto& eg: adj2[v]){
int u = eg.first;
if(u==e){
eg.second = n-var-1;
}
}
return;
}
int real_pos;
int visit2(int v){
if(vis[v]==-1){
real_pos = v;
return vis[v] = visit(v+1);
}
return vis[v];
}
void locate(vector<pair<int, int>> F, int curr, int t) {
adj2.resize(n);
vis.resize(n, -1);
for(int i = 0; i<n-1; i++){
adj2[F[i].first-1].push_back({F[i].second-1, -1});
adj2[F[i].second-1].push_back({F[i].first-1, -1});
}
curr--;
calcsiz2(curr, curr);
calcsiz3(curr, curr);
int v = curr;
real_pos = v;
vis[curr]=t;
while(1){
sort(adj2[v].begin(), adj2[v].end(), [](auto a, auto b){
return a.second > b.second;
});
if(t){
v = adj2[v][0].first;
t = visit2(v);
}
else{
if(adj2[v].size()<2) return;
if(adj2[v][0].second==adj2[v][1].second){
t = visit2(adj2[v][0].first);
if(t==1){
t = visit2(v);
if(real_pos!=v){
visit(v+1);
real_pos = v;
}
if(adj2[v].size()<2) return;
t = visit2(adj2[v][1].first);
if(t==1){
t = visit2(v);
if(real_pos!=v){
visit(v+1);
real_pos = v;
}
if(adj2[v].size()<3) return;
t = visit2(adj2[v][2].first);
if(t==1){
visit2(v);
if(real_pos!=v){
visit(v+1);
real_pos = v;
}
return;
}
else v = adj2[v][2].first;
}
else v = adj2[v][1].first;
}
else v = adj2[v][0].first;
}
else{
t = visit2(adj2[v][1].first);
if(t==1){
t = visit2(v);
if(real_pos!=v){
visit(v+1);
real_pos = v;
}
if(adj2[v].size()<3) return;
t = visit2(adj2[v][2].first);
if(t==1){
visit2(v);
if(real_pos!=v){
visit(v+1);
real_pos = v;
}
return;
}
else v = adj2[v][2].first;
}
else v = adj2[v][1].first;
}
}
}
}
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 |
Execution timed out |
3058 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3039 ms |
7436 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3006 ms |
3856 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3058 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
