#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
int i,j,s,t;
int a[261523],b[234567],l,r,tt,k,y,z,n,m,x,MAXN=123456;
vector<int>te,so, hursh[212334],an;
struct node {
int endP[2], par, size, val;//*, deed oroi, hemjee, utga
} comp[MAXN];
int wpar[MAXN], depth[MAXN];//deed oroitoigoo holbogdoh urt, gun
vector <int> adj[MAXN];//hurshuud
int root(int u) {
while (comp[u].par >= 0) u = comp[u].par;
return u;//odoogoor hamgiin deed undes
}
bool join(int u, int v, int w) {//u, v, oroinuudiig w utgaar holboh
int x = root(u), y = root(v);//deed undsuudiig ni oloh
if (x == y) {//holbogdson bol
if (comp[x].val < 0) comp[x].val = w;//x ni utga avaagui bol w utgiig olgoh
return false;//
}
if (comp[x].size < comp[y].size) {
swap(x, y); swap(u, v);//ali olon oroitoi olonlogiig i u bolgoh
}
comp[x].size += comp[y].size; comp[y].par = x;//negtgeh, y-iin deed oroig x bolgoh
wpar[y] = w; adj[x].push_back(y);//deed oroitoigoo holbogdoh urt w, xiin hursh y
if (comp[x].val < 0 && comp[y].val < 0 &&
(u == comp[x].endP[0] || u == comp[x].endP[1]) &&
(v == comp[y].endP[0] || v == comp[y].endP[1])) {
if (u == comp[x].endP[0])
comp[x].endP[0] = comp[x].endP[1];
if (v == comp[y].endP[0])
comp[x].endP[1] = comp[y].endP[1];
else comp[x].endP[1] = comp[y].endP[0];
} else if (comp[x].val < 0) comp[x].val = w;
return true;
}
void DFS(int u) {
for (int v : adj[u]) {
depth[v] = depth[u] + 1; DFS(v);//guniig ni dfs ashiglaj oloh
}
}
void init(int N, int M, vector <int> U, vector <int> V, vector <int> W) {
vector <int> sorted(M);
for (i = 0; i <M; i ++)
sorted[i]=i;
sort(sorted.begin(), sorted.end(),[&](int i, int j) {return W[i] < W[j];});
for (int i = 0; i < N; i++) {
comp[i].endP[0] = comp[i].endP[1] = i;
comp[i].par = -1; comp[i].size = 1;
comp[i].val = -1;
}
for (int i : sorted) join(U[i], V[i], W[i]);
for (int i = 0; i < N; i++)
if (comp[i].par < 0) DFS(i);
}
int getMinimumFuelCapacity(int u, int v) {
if (root(u) != root(v)) return -1;
int res = 0;
while (u != v) {
if (depth[u] < depth[v]) swap(u, v);
res = max(res, wpar[u]); u = comp[u].par;
}
while (u >= 0 && comp[u].val < 0) {
res = max(res, wpar[u]); u = comp[u].par;
}
if (u < 0) return -1;
return max(res, comp[u].val);
}
Compilation message
swap.cpp:10:12: error: array bound is not an integer constant before ']' token
10 | } comp[MAXN];
| ^
swap.cpp:12:14: error: array bound is not an integer constant before ']' token
12 | int wpar[MAXN], depth[MAXN];//deed oroitoigoo holbogdoh urt, gun
| ^
swap.cpp:12:27: error: array bound is not an integer constant before ']' token
12 | int wpar[MAXN], depth[MAXN];//deed oroitoigoo holbogdoh urt, gun
| ^
swap.cpp:13:22: error: array bound is not an integer constant before ']' token
13 | vector <int> adj[MAXN];//hurshuud
| ^
swap.cpp: In function 'int root(int)':
swap.cpp:16:12: error: 'comp' was not declared in this scope
16 | while (comp[u].par >= 0) u = comp[u].par;
| ^~~~
swap.cpp: In function 'bool join(int, int, int)':
swap.cpp:23:13: error: 'comp' was not declared in this scope
23 | if (comp[x].val < 0) comp[x].val = w;//x ni utga avaagui bol w utgiig olgoh
| ^~~~
swap.cpp:26:9: error: 'comp' was not declared in this scope
26 | if (comp[x].size < comp[y].size) {
| ^~~~
swap.cpp:29:5: error: 'comp' was not declared in this scope
29 | comp[x].size += comp[y].size; comp[y].par = x;//negtgeh, y-iin deed oroig x bolgoh
| ^~~~
swap.cpp:30:5: error: 'wpar' was not declared in this scope
30 | wpar[y] = w; adj[x].push_back(y);//deed oroitoigoo holbogdoh urt w, xiin hursh y
| ^~~~
swap.cpp:30:18: error: 'adj' was not declared in this scope
30 | wpar[y] = w; adj[x].push_back(y);//deed oroitoigoo holbogdoh urt w, xiin hursh y
| ^~~
swap.cpp: In function 'void DFS(int)':
swap.cpp:43:18: error: 'adj' was not declared in this scope
43 | for (int v : adj[u]) {
| ^~~
swap.cpp:44:9: error: 'depth' was not declared in this scope
44 | depth[v] = depth[u] + 1; DFS(v);//guniig ni dfs ashiglaj oloh
| ^~~~~
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:55:9: error: 'comp' was not declared in this scope
55 | comp[i].endP[0] = comp[i].endP[1] = i;
| ^~~~
swap.cpp:62:13: error: 'comp' was not declared in this scope
62 | if (comp[i].par < 0) DFS(i);
| ^~~~
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:69:13: error: 'depth' was not declared in this scope
69 | if (depth[u] < depth[v]) swap(u, v);
| ^~~~~
swap.cpp:70:24: error: 'wpar' was not declared in this scope
70 | res = max(res, wpar[u]); u = comp[u].par;
| ^~~~
swap.cpp:70:38: error: 'comp' was not declared in this scope
70 | res = max(res, wpar[u]); u = comp[u].par;
| ^~~~
swap.cpp:72:22: error: 'comp' was not declared in this scope
72 | while (u >= 0 && comp[u].val < 0) {
| ^~~~
swap.cpp:73:24: error: 'wpar' was not declared in this scope
73 | res = max(res, wpar[u]); u = comp[u].par;
| ^~~~
swap.cpp:76:21: error: 'comp' was not declared in this scope
76 | return max(res, comp[u].val);
| ^~~~
