#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 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 (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[0]){
ties[i-1] = 0;
}else{
ties[i-1] = 1;
}
}
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;
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){
// 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 (here==0){
// if (visited[curr]==2) curr = idk[1][1], here = visit(curr);
// else curr = idk[0][1], here = visit(curr);
// }else{
// if (visited[curr]==2) curr = idk[idk.size()-2][1], here = visit(curr);
// else curr = idk[idk.size()-1][1], here = visit(curr);
// }
// }
// return;
}
Compilation message
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:98:8: warning: unused variable 'n' [-Wunused-variable]
98 | ll n = F.size()+1;
| ^
incursion.cpp:99:8: warning: unused variable 'here' [-Wunused-variable]
99 | ll here = t;
| ^~~~
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);
| ~~~~~~~~~~~~~~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
29552 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
150 ms |
37608 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
129 ms |
35336 KB |
Partially correct |
| 2 |
Incorrect |
128 ms |
35232 KB |
Not correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
29552 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
