#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
#define ll long long
#define sz(s) (int)s.size()
#define ff first
#define ss second
const int N = 400005;
vector <pair<int,pair<int,int>>> v;
int p[N], sp[N][40], p1[N], depth[N], cnt = 0, com[N];
pair <int,int> c[N], d[N];
vector <int> v1[N], v2[N];
int f(int z){
for(int i = 30; i >= 0; i--){
if(c[sp[z][i]].ff != 1){
z = sp[z][i];
}
}
if(z == p1[z]) return -1;
z = p1[z];
return c[z].ss;
}
void dfs(int x){
com[x] = cnt;
for(auto i : v2[x]){
depth[i] = depth[x]+1;
dfs(i);
}
}
int fnd(int x){
if(x == p[x]) return x;
return p[x] = fnd(p[x]);
}
int lca(int x, int y){
if(depth[x] < depth[y]) swap(x,y);
for(int i = 30; i >= 0; i--){
if(depth[x] - (1<<i) >= depth[y]){
x = sp[x][i];
}
}
for(int i = 30; i >= 0; i--){
if(sp[x][i] != sp[y][i]){
x = sp[x][i];
y = sp[y][i];
}
}
return sp[x][0];
}
void init(int n, int m, vector<int> u1, vector<int> v1, vector<int> w1) {
for(int i = 0; i < m; i++){
v.push_back({w1[i],{u1[i],v1[i]}});
}
sort(v.begin(), v.end());
for(int i = 0; i <= n+m; i++){
p[i] = i;
c[i] = {0,0};
d[i] = {i,i};
}
int cn = n;
for(int i = 0; i < sz(v); i++){
auto x = v[i].ss;
int a = fnd(p[x.ff]), b = fnd(p[x.ss]);
cn++;
if(c[a].ff + c[b].ff != 0){
p[a] = cn;
p1[a] = cn;
p[b] = cn;
p1[b] = cn;
c[cn] = {1,v[i].ff};
v2[cn].push_back(a);
if(a != b) v2[cn].push_back(b);
}
else {
if(a == b){
c[cn] = {1,v[i].ff};
p[a] = cn;
p1[a] = cn;
v2[cn].push_back(a);
}
else {
v2[cn].push_back(a);
v2[cn].push_back(b);
p[a] = cn;
p1[a] = cn;
p[b] = cn;
p1[b] = cn;
bool tr1 = (d[a].ff == x.ff or d[a].ff == x.ss), tr11 = (d[a].ss == x.ff or d[a].ss == x.ss);
bool tr2 = (d[b].ff == x.ff or d[b].ff == x.ss), tr22 = (d[b].ss == x.ff or d[b].ss == x.ss);
if(tr1+tr11+tr2+tr22 == 2){
c[cn] = {0,v[i].ff};
if(tr1 == 1) d[cn] = {d[a].ss,0};
else d[cn] = {d[a].ff,0};
if(tr2 == 1) d[cn] = {0,d[b].ss};
else d[cn] = {0,d[b].ff};
}
else {
c[cn] = {1,v[i].ff};
}
}
}
}
for(int i = cn; i >= 0; i--){
if(depth[i] == 0){
cnt++;
dfs(i);
}
}
for(int i = 0; i <= cn; i++){
sp[i][0] = p1[i];
}
for(int j = 1; j <= 30; j++){
for(int i = 0; i <= cn; i++){
if(1<<j > depth[i]) continue;
sp[i][j] = (sp[sp[i][j-1]][j-1]);
}
}
}
int getMinimumFuelCapacity(int x, int y) {
if(com[x] != com[y]) return -1;
int z = lca(x,y);
return f(z);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
