#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 2e5 + 5, mod = 1e9 + 7; //!
int t, p[N], need[N], rep[N], id[N], d[N], n, vis[N], par[N],rep2[N], f[N];
int room[N];
//int n;
vector<int>adj[N];
vector<pair<int, pair<int, pii> > > V[25];
int find(int u) {
return (par[u] == u ? u : par[u] = find(par[u]));
}
void merge(int u, int v) {
u = find(u), v = find(v);
par[u] = v;
}
void dfs(int u, int P) {
p[u] = P;
for(int i = 0; i < V[u].size(); i++) {
if(V[u][i].f == p[u]) continue;
rep[V[u][i].f] = V[u][i].s.s.f;
rep2[V[u][i].f] = V[u][i].s.s.s;
room[V[u][i].f] = V[u][i].s.f;
dfs(V[u][i].f, u);
}
}
int dist(int u,int v) {
queue<int> q;
for(int i = 1; i <= n; i++) d[i] = n + 5;
d[u] = 0;
q.push(u);
while(q.size()) {
int u = q.front();
q.pop();
for(int i = 0; i < adj[u].size(); i++) {
if(d[adj[u][i]] == n + 5) {
d[adj[u][i]] = d[u] + 1;
q.push(adj[u][i]);
}
}
}
return d[v];
}
main() {
// ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n;
int S, T;
cin >> S >> T;
vector< pair<pii, int> > E;
for(int i = 1; i <= n; i++) par[i] = i;
for(int i = 2; i <= n; i++) {
int u, v, t;
cin >> u >> v >> t;
adj[u].push_back(v);
adj[v].push_back(u);
if(t) {
E.push_back({{u,v}, t});
}
else merge(u, v);
}
int cur = 0;
for(int i = 1; i <= n; i++) {
if(find(i) == i) {
id[i] = ++cur;
}
}
for(int i = 0; i < E.size(); i++) {
V[id[find(E[i].f.f)]].push_back({id[find(E[i].f.s)], {E[i].s, {E[i].f.f, E[i].f.s}}});
V[id[find(E[i].f.s)]].push_back({id[find(E[i].f.f)], {E[i].s, {E[i].f.s, E[i].f.f}}});
}
dfs(id[find(S)], 0);
vis[id[find(S)]] = 1;
int u = id[find(T)];
stack<int> s;
vector<int> v;
f[u] = 1;
while(!vis[u]) {
s.push(u);
need[u] = 1;
u = p[u];
}
cur = S;
int ans = 0, cc = 0;
while(s.size()) {
int u = s.top(), x = room[u];
if(vis[u]) continue;
++cc;
if(cc > 25) {
cout << -1;
return 0;
}
if(vis[id[find(x)]]) {
ans += dist(cur, x) + dist(x, rep[u]);
vis[u] = 1;
if(f[u]) ++ans, cur = rep2[u], --f[u];
else cur = rep[u];
need[u] = 0;
s.pop();
continue;
}
vector<int> v;
x = id[find(x)];
f[x]++;
while(!vis[x]) {
s.push(x);
x = p[x];
}
}
ans += dist(cur, T);
cout << ans;
}
Compilation message
Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:23:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, std::pair<long long int, long long int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
Main.cpp: In function 'long long int dist(long long int, long long int)':
Main.cpp:41:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i = 0; i < adj[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
50 | main() {
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:74:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i = 0; i < E.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
138 ms |
10380 KB |
Output is correct |
| 4 |
Correct |
148 ms |
10688 KB |
Output is correct |
| 5 |
Correct |
127 ms |
10700 KB |
Output is correct |
| 6 |
Correct |
161 ms |
10776 KB |
Output is correct |
| 7 |
Correct |
186 ms |
10704 KB |
Output is correct |
| 8 |
Correct |
198 ms |
10700 KB |
Output is correct |
| 9 |
Correct |
194 ms |
10760 KB |
Output is correct |
| 10 |
Correct |
184 ms |
10692 KB |
Output is correct |
| 11 |
Correct |
205 ms |
10684 KB |
Output is correct |
| 12 |
Correct |
173 ms |
10216 KB |
Output is correct |
| 13 |
Incorrect |
171 ms |
10220 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
4948 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
138 ms |
10380 KB |
Output is correct |
| 4 |
Correct |
148 ms |
10688 KB |
Output is correct |
| 5 |
Correct |
127 ms |
10700 KB |
Output is correct |
| 6 |
Correct |
161 ms |
10776 KB |
Output is correct |
| 7 |
Correct |
186 ms |
10704 KB |
Output is correct |
| 8 |
Correct |
198 ms |
10700 KB |
Output is correct |
| 9 |
Correct |
194 ms |
10760 KB |
Output is correct |
| 10 |
Correct |
184 ms |
10692 KB |
Output is correct |
| 11 |
Correct |
205 ms |
10684 KB |
Output is correct |
| 12 |
Correct |
173 ms |
10216 KB |
Output is correct |
| 13 |
Incorrect |
171 ms |
10220 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
