oj.uz

Submission #936225

# Submission time Handle Problem Language Result Execution time Memory
936225 2024-03-01T12:32:40 Z winter0101 Rigged Roads (NOI19_riggedroads) C++14
100 / 100
 379 ms 65684 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=3e5+9;
vector<pii>a[maxn];
int st[maxn][21],d[maxn];
pii pr[maxn];
void dfs(int u,int par){
for (auto v:a[u]){
if (v.fi==par)continue;
pr[v.fi]={u,v.se};
st[v.fi][0]=u;
for1(i,1,20)st[v.fi][i]=st[st[v.fi][i-1]][i-1];
d[v.fi]=d[u]+1;
dfs(v.fi,u);
}
}
pii b[maxn];
int lca(int u,int v){
if (d[u]<d[v])swap(u,v);
int k=d[u]-d[v];
for1(i,0,20)if (k>>i&1)u=st[u][i];
if (u==v)return u;
for2(i,20,0){
if (!st[u][i]||!st[v][i])continue;
if (st[u][i]!=st[v][i]){
u=st[u][i];
v=st[v][i];
}
}
return st[u][0];
}
bool use[maxn];
int ans[maxn];
int f[maxn];
int fs(int u){
if (f[u]<0)return u;
return f[u]=fs(f[u]);
}
void unite(int u,int v){
u=fs(u),v=fs(v);
if (u==v)return;
f[v]+=f[u];
f[u]=v;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int n,m;
    cin>>n>>m;
    for1(i,1,m)cin>>b[i].fi>>b[i].se;
    for1(i,1,n)f[i]=-1;
    for1(i,1,n-1){
    int id;
    cin>>id;
    use[id]=1;
    a[b[id].fi].pb({b[id].se,id});
    a[b[id].se].pb({b[id].fi,id});
    }
    dfs(1,0);
    vector<int>perm;
    auto take=[&](int id){
    int u=b[id].fi,v=b[id].se,t=lca(u,v);
    vector<int>xd;
    while (fs(u)!=fs(t)){
    u=fs(u);
    xd.pb(pr[u].se);
    unite(u,pr[u].fi);
    u=fs(pr[u].fi);
    }
    while (fs(v)!=fs(t)){
    v=fs(v);
    xd.pb(pr[v].se);
    unite(v,pr[v].fi);
    v=fs(pr[v].fi);
    }
    sort(all(xd));
    for (auto v1:xd)perm.pb(v1);
    if (!use[id])perm.pb(id);
    };
    for1(i,1,m){
    take(i);
    }
    int cnt=0;
    for (auto v:perm)ans[v]=++cnt;
    for1(i,1,m)cout<<ans[i]<<" ";
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 3 ms 15708 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 3 ms 15708 KB Output is correct
4 Correct 4 ms 15708 KB Output is correct
5 Correct 4 ms 15708 KB Output is correct
6 Correct 4 ms 15964 KB Output is correct
7 Correct 3 ms 15708 KB Output is correct
8 Correct 4 ms 15964 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 27808 KB Output is correct
2 Correct 84 ms 33756 KB Output is correct
3 Correct 69 ms 19628 KB Output is correct
4 Correct 160 ms 54620 KB Output is correct
5 Correct 159 ms 58040 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 37436 KB Output is correct
2 Correct 56 ms 24312 KB Output is correct
3 Correct 26 ms 19356 KB Output is correct
4 Correct 59 ms 33032 KB Output is correct
5 Correct 22 ms 22648 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 57188 KB Output is correct
2 Correct 183 ms 65556 KB Output is correct
3 Correct 42 ms 29804 KB Output is correct
4 Correct 70 ms 35948 KB Output is correct
5 Correct 247 ms 65684 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 45356 KB Output is correct
2 Correct 136 ms 36432 KB Output is correct
3 Correct 331 ms 61012 KB Output is correct
4 Correct 309 ms 56264 KB Output is correct
5 Correct 18 ms 19548 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 3 ms 15708 KB Output is correct
4 Correct 4 ms 15708 KB Output is correct
5 Correct 4 ms 15708 KB Output is correct
6 Correct 4 ms 15964 KB Output is correct
7 Correct 3 ms 15708 KB Output is correct
8 Correct 4 ms 15964 KB Output is correct
9 Correct 52 ms 27808 KB Output is correct
10 Correct 84 ms 33756 KB Output is correct
11 Correct 69 ms 19628 KB Output is correct
12 Correct 160 ms 54620 KB Output is correct
13 Correct 159 ms 58040 KB Output is correct
14 Correct 77 ms 37436 KB Output is correct
15 Correct 56 ms 24312 KB Output is correct
16 Correct 26 ms 19356 KB Output is correct
17 Correct 59 ms 33032 KB Output is correct
18 Correct 22 ms 22648 KB Output is correct
19 Correct 211 ms 57188 KB Output is correct
20 Correct 183 ms 65556 KB Output is correct
21 Correct 42 ms 29804 KB Output is correct
22 Correct 70 ms 35948 KB Output is correct
23 Correct 247 ms 65684 KB Output is correct
24 Correct 171 ms 45356 KB Output is correct
25 Correct 136 ms 36432 KB Output is correct
26 Correct 331 ms 61012 KB Output is correct
27 Correct 309 ms 56264 KB Output is correct
28 Correct 18 ms 19548 KB Output is correct
29 Correct 343 ms 56768 KB Output is correct
30 Correct 379 ms 59916 KB Output is correct
31 Correct 334 ms 56496 KB Output is correct
32 Correct 89 ms 22168 KB Output is correct
33 Correct 297 ms 57572 KB Output is correct