#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];
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;
while(!vis[u]) {
s.push(u);
need[u] = 1;
u = p[u];
}
cur = S;
int ans = 0;
while(s.size()) {
int u = s.top(), x = room[u];
if(vis[id[find(x)]]) {
ans += dist(cur, x) + dist(x, rep[u]);
vis[u] = 1;
// cout << cur << " --> " << x << " " << x << " --? " << rep[u] << endl; cout << ans << endl;
if(V[u].size() == 1) ++ans, cur = rep2[u];
else cur = rep[u];
need[u] = 0;
s.pop();
continue;
}
vector<int> v;
x = id[find(x)];
while(!vis[x]) {
if(need[x]) {
cout << -1;
return 0;
}
need[x] = 1;
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 |
141 ms |
10384 KB |
Output is correct |
| 4 |
Correct |
190 ms |
10460 KB |
Output is correct |
| 5 |
Correct |
154 ms |
10440 KB |
Output is correct |
| 6 |
Correct |
153 ms |
10500 KB |
Output is correct |
| 7 |
Correct |
252 ms |
10520 KB |
Output is correct |
| 8 |
Correct |
168 ms |
10520 KB |
Output is correct |
| 9 |
Correct |
163 ms |
10508 KB |
Output is correct |
| 10 |
Correct |
193 ms |
10524 KB |
Output is correct |
| 11 |
Correct |
227 ms |
10452 KB |
Output is correct |
| 12 |
Correct |
148 ms |
10036 KB |
Output is correct |
| 13 |
Incorrect |
155 ms |
9936 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5076 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 |
141 ms |
10384 KB |
Output is correct |
| 4 |
Correct |
190 ms |
10460 KB |
Output is correct |
| 5 |
Correct |
154 ms |
10440 KB |
Output is correct |
| 6 |
Correct |
153 ms |
10500 KB |
Output is correct |
| 7 |
Correct |
252 ms |
10520 KB |
Output is correct |
| 8 |
Correct |
168 ms |
10520 KB |
Output is correct |
| 9 |
Correct |
163 ms |
10508 KB |
Output is correct |
| 10 |
Correct |
193 ms |
10524 KB |
Output is correct |
| 11 |
Correct |
227 ms |
10452 KB |
Output is correct |
| 12 |
Correct |
148 ms |
10036 KB |
Output is correct |
| 13 |
Incorrect |
155 ms |
9936 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
