#include "incursion.h"
#include <bits/stdc++.h>
//#include "sample_grader.cpp"
using namespace std;
//#define int long long
//#define ld long double
#define show(x,y) cerr << y << " " << #x << endl;
#define show2(x,y,i,j) cerr << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cerr << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cerr << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
int n;
vector<int>adj[45005];
int pp[45005];
int sz[45005];
void dfs(int index, int par){
sz[index]=1;
for(auto it:adj[index]){
if(it==par) continue;
pp[it]=index;
dfs(it,index);
sz[index]+=sz[it];
}
}
vector<int>mark(vector<pair<int, int>> F, int safe){
n=F.size()+1;
for(int x=0;x<n-1;x++){
adj[F[x].first].push_back(F[x].second);
adj[F[x].second].push_back(F[x].first);
}
int rt=0;
for(int x=1;x<=n;x++){
if(adj[x].size()==2){
dfs(x,-1);
rt=x;
}
}
//show(rt,rt);
vector<int>ans(n,0);
int cur=safe;
int take=-1;
while(cur){
ans[cur-1]=1;
if(take==-1){
ans[cur-1]=1;
if(cur==rt) break;
take=cur;
cur=pp[cur];
}
else{
show2(cur,cur,take,take);
int nxt=sz[cur]-sz[take]-1;
show2(sz[take],sz[take],nxt,nxt);
if(sz[take]<nxt){
ans[cur-1]=1;
}
else ans[cur-1]=2;
if(cur==rt) break;
take=cur;
cur=pp[cur];
}
}
show4(ans,ans);
return ans;
}
//visit()
void locate(vector<pair<int, int>> F, int curr, int t){
n=F.size()+1;
for(int x=0;x<=n;x++){
adj[x].clear();
}
for(int x=0;x<n-1;x++){
adj[F[x].first].push_back(F[x].second);
adj[F[x].second].push_back(F[x].first);
}
memset(pp,0,sizeof(pp));
memset(sz,0,sizeof(sz));
for(int x=1;x<=n;x++){
if(adj[x].size()==2){
dfs(x,-1);
}
}
bool done[n+5];
memset(done,0,sizeof(done));
while(1){
show2(curr,curr,t,t);
done[curr]=true;
if(t==0){
//go up
done[curr]=true;
t=visit(pp[curr]);
curr=pp[curr];
}
else if(t==1){
//go small
bool amos=false;
pii mini={1e15,1e15};
for(auto it:adj[curr]){
if(it==pp[curr]) continue;
if(done[it]) continue;
mini=min(mini,{sz[it],it});
amos=true;
}
if(!amos||done[mini.second]) return;
t=visit(mini.second);
curr=mini.second;
}
else{
//go big
pii maxi={-1e15,1e15};
bool amos=false;
for(auto it:adj[curr]){
if(it==pp[curr]) continue;
if(done[it]) continue;
maxi=max(maxi,{sz[it],it});
amos=true;
}
if(!amos||done[maxi.second]) return;
t=visit(maxi.second);
curr=maxi.second;
}
}
}
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 |
1 ms |
1368 KB |
Security violation! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3026 ms |
7428 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
130 ms |
4172 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1368 KB |
Security violation! |
| 2 |
Halted |
0 ms |
0 KB |
- |
