#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("HAMMING.INP");
ofstream fout("HAMMING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e18 + 7, inf = 1e16;
const int mxn = 5e3 + 5, sq = 400;
int n, e;
vt<pii>adj[mxn + 1];
bool ok[mxn + 1];
int special[mxn + 1], dep[mxn + 1], up[mxn + 1][19], toedge[mxn + 1], ans[mxn + 1];
pii edge[mxn + 1];
void dfs(int s, int pre){
for(auto [i, id]: adj[s]){
if(i != pre){
dep[i] = dep[s] + 1;
up[i][0] = s; toedge[i] = id;
dfs(i, s);
}
}
}
int lca(int u, int v){
if(dep[u] < dep[v])swap(u, v);;
int k = dep[u] - dep[v];
for(int i = 0; i < 19; i++){
if(k & (1 << i)){
u = up[u][i];
}
}
if(u == v)return(u);
for(int i = 18; i >= 0; i--){
if(up[u][i] != up[v][i]){
u = up[u][i]; v = up[v][i];
}
}
return(up[u][0]);
}
struct DSU{
int p[mxn + 1], sz[mxn + 1];
void init(){
for(int i = 1; i <= mxn; i++){
p[i] = i; sz[i] = 1;
}
}
int fp(int u){
if(p[u] == u)return(u);
return(p[u] = fp(p[u]));
}
void unon(int a, int b){
a = fp(a); b = fp(b);
if(a == b)return;
if(dep[a] > dep[b])swap(a, b);
p[b] = a; sz[a] += sz[b];
}
};
DSU dsu;
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> e;
dsu.init();
for(int i = 0; i < e; i++){
cin >> edge[i].fi >> edge[i].se; ans[i] = -1;
}
for(int i = 1; i < n; i++){
cin >> special[i]; special[i]--; auto [u, v] = edge[special[i]]; ok[special[i]] = 1;
adj[u].pb(make_pair(v, special[i])); adj[v].pb(make_pair(u, special[i]));
}
dfs(1, -1);
for(int i = 1; i < 19; i++){
for(int j = 1; j <= n; j++){
up[j][i] = up[up[j][i - 1]][i - 1];
}
}
int mn = 1;
for(int i = 0; i < e; i++){
auto [u, v] = edge[i];
if(ans[i] != -1)continue;
if(ok[i]){
dsu.unon(u, v);
ans[i] = mn++; continue;
}
int l = lca(u, v);
vt<int>change;
while(1){
int tou = dsu.fp(u);
if(dep[tou] <= dep[l])break;
change.pb(toedge[tou]);
auto [uu, vv] = edge[toedge[tou]];
dsu.unon(uu, vv);
}
while(1){
int tov = dsu.fp(v);
if(dep[tov] <= dep[l])break;
change.pb(toedge[tov]);
auto [uu, vv] = edge[toedge[tov]];
dsu.unon(uu, vv);
//cout << tov << " ";
}
sort(change.begin(), change.end());
for(auto j: change){
ans[j] = mn++;
}
ans[i] = mn++;
}
for(int i = 0; i < e; i++){
cout << ans[i] << " ";
}
return(0);
}
Compilation message
riggedroads.cpp: In function 'void dfs(int, int)':
riggedroads.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
30 | for(auto [i, id]: adj[s]){
| ^
riggedroads.cpp: In function 'int main()':
riggedroads.cpp:82:47: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
82 | cin >> special[i]; special[i]--; auto [u, v] = edge[special[i]]; ok[special[i]] = 1;
| ^
riggedroads.cpp:93:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
93 | auto [u, v] = edge[i];
| ^
riggedroads.cpp:106:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
106 | auto [uu, vv] = edge[toedge[tou]];
| ^
riggedroads.cpp:115:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
115 | auto [uu, vv] = edge[toedge[tov]];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
456 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
592 KB |
Output is correct |
| 6 |
Correct |
1 ms |
596 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| 8 |
Correct |
1 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
2608 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
2892 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
2852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
2864 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
456 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
592 KB |
Output is correct |
| 6 |
Correct |
1 ms |
596 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| 8 |
Correct |
1 ms |
596 KB |
Output is correct |
| 9 |
Runtime error |
9 ms |
2608 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
