#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> mark(vector <pair <int,int> > F,int safe){
int n=F.size()+1;
vector <int> g[n];
for (auto&i:F){
i.first--; i.second--;
g[i.first].push_back(i.second);
g[i.second].push_back(i.first);
}
safe--;
vector <int> dist(n,-1);
queue <int> q;
q.push(safe);
dist[safe]=0;
while (!q.empty()){
int tp=q.front(); q.pop();
for (int i:g[tp]){
if (dist[i]==-1){
dist[i]=(dist[tp]+1)%3;
q.push(i);
}
}
}
return dist;
}
int n,sz[50000];
vector <int> g[50000];
vector <pair <int,int> > vsz[50000];
void dfs0(int cur,int prv){
sz[cur]=1;
for (int i:g[cur]){
if (i==prv) continue;
dfs0(i,cur);
sz[cur]+=sz[i];
}
}
void chroot(int nw,int ol){
sz[ol]-=sz[nw];
sz[nw]+=sz[ol];
}
void dfs1(int cur,int prv){
if (vsz[cur].empty()){
for (int i:g[cur]) vsz[cur].push_back({sz[i],i});
sort(vsz[cur].begin(),vsz[cur].end(),greater <pair <int,int> >());
}
for (int i:g[cur]){
if (i==prv) continue;
chroot(i,cur);
dfs1(i,cur);
chroot(cur,i);
}
}
void locate(vector <pair <int,int> > F,int curr,int t){
n=F.size()+1;
for (auto&i:F){
i.first--; i.second--;
g[i.first].push_back(i.second);
g[i.second].push_back(i.first);
}
curr--;
dfs0(0,-1);
dfs1(0,-1);
map <int,int> mp;
mp[curr]=t;
while (1){
bool done=0;
for (pair <int,int> i:vsz[curr]){
if (mp.find(i.second)!=mp.end()) continue;
int tp=visit(i.second+1);
mp[i.second]=tp;
if (tp!=(mp[curr]+2)%3){
visit(curr+1);
} else {
curr=tp;
done=1;
break;
}
}
if (!done) break;
}
}
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 |
2 ms |
5384 KB |
Not correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
87 ms |
14916 KB |
Not correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
87 ms |
12776 KB |
Partially correct |
2 |
Incorrect |
89 ms |
12700 KB |
Not correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
5384 KB |
Not correct |
2 |
Halted |
0 ms |
0 KB |
- |