oj.uz

Submission #936130

# Submission time Handle Problem Language Result Execution time Memory
936130 2024-03-01T07:54:25 Z vjudge1 Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 440 ms 96160 KB 
#include<bits/stdc++.h>
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxn=3e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
bool ins[maxn];
ll lab[maxn],top[maxn],P[maxn][20];
ll findset(ll x)
{
    return lab[x]<0?x:lab[x]=findset(lab[x]);
}
vector<pli>g[maxn];
ll h[maxn];
void unite(ll u,ll v)
{
    u=findset(u);
    v=findset(v);
    if(u==v) return;
    if(lab[u]>lab[v]) swap(u,v);
    lab[u]+=lab[v];
    lab[v]=u;
    if(h[top[u]]>h[top[v]]) top[u]=top[v];
}
ll idx[maxn];
void dfs(ll u,ll p)
{
    P[u][0]=p;
    for(int i=1;i<=18;i++) P[u][i]=P[P[u][i-1]][i-1];
    for(auto [v,id]:g[u])
    {
        if(v!=p)
        {
            h[v]=h[u]+1;
            idx[v]=id;
            dfs(v,u);
        }
    }
}
void update(ll u)
{
    ins[u]=true;
    top[u]=u;
    for(auto [v,id]:g[u])
    {
        if(ins[v]==true) unite(u,v);
    }
}
ll par[maxn];
vector<pli>get(ll u,ll p)
{
    vector<pli>ans;
    while(h[u]>h[p])
    {
        if(ins[u]==true)
        {
            u=top[findset(u)];
            u=P[u][0];
        }
        else
        {
            ans.pb({u,idx[u]});
            u=P[u][0];
        }
    }
    return ans;
}
ll n,e,x[maxn],y[maxn];
bool in[maxn];
ll ans[maxn];
ll lca(ll u,ll v)
{
    if(h[u]<h[v]) swap(u,v);
    for(int i=18;i>=0;i--) if(h[u]-(1<<i)>=h[v]) u=P[u][i];
    if(u==v) return u;
    for(int i=18;i>=0;i--) if(P[u][i]!=P[v][i]) u=P[u][i],v=P[v][i];
    return P[u][0];
}
bool cmp(pli x,pli y)
{
    return x.se<y.se;
}
void solve()
{
    cin >> n >> e;
    for(int i=1;i<=n;i++) lab[i]=-1;
    for(int i=1;i<=e;i++)
    {
        cin >> x[i] >> y[i];
        in[i]=false;
    }
    for(int i=1;i<n;i++)
    {
        ll id;
        cin >> id;
        in[id]=true;
        g[x[id]].pb({y[id],id});
        g[y[id]].pb({x[id],id});
    }
    dfs(1,0);
    ll dien=0;
    for(int i=1;i<=e;i++)
    {
        if(ans[i]>0) continue;
        if(in[i]==false)
        {
            ll u=x[i];
            ll v=y[i];
            ll c=lca(u,v);
            vector<pli>cc=get(u,c);
            vector<pli>vc=get(v,c);
            for(auto zz:vc) cc.pb(zz);
            sort(cc.begin(),cc.end(),cmp);
            for(auto zz:cc)
            {
                update(zz.fi);
                ans[zz.se]=++dien;
            }
            ans[i]=++dien;
        }
        else
        {
            ll u=x[i];
            ll v=y[i];
            if(h[u]<h[v]) swap(u,v);
            update(u);
            ans[i]=++dien;
        }
    }
    for(int i=1;i<=e;i++)
    {
        cout << ans[i]<<' ';
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Subtask #1
8.0 / 8.0

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

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 5 ms 22876 KB Output is correct
4 Correct 6 ms 23120 KB Output is correct
5 Correct 6 ms 22876 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct
7 Correct 4 ms 22876 KB Output is correct
8 Correct 4 ms 23052 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 44488 KB Output is correct
2 Correct 99 ms 52680 KB Output is correct
3 Correct 87 ms 29904 KB Output is correct
4 Correct 120 ms 84400 KB Output is correct
5 Correct 129 ms 85688 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 53144 KB Output is correct
2 Correct 57 ms 35692 KB Output is correct
3 Correct 31 ms 29464 KB Output is correct
4 Correct 73 ms 45900 KB Output is correct
5 Correct 25 ms 32916 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 83676 KB Output is correct
2 Correct 202 ms 92928 KB Output is correct
3 Correct 44 ms 42832 KB Output is correct
4 Correct 70 ms 50696 KB Output is correct
5 Correct 292 ms 96160 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 64928 KB Output is correct
2 Correct 106 ms 52192 KB Output is correct
3 Correct 344 ms 88092 KB Output is correct
4 Correct 303 ms 84148 KB Output is correct
5 Correct 20 ms 30808 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 5 ms 22876 KB Output is correct
4 Correct 6 ms 23120 KB Output is correct
5 Correct 6 ms 22876 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct
7 Correct 4 ms 22876 KB Output is correct
8 Correct 4 ms 23052 KB Output is correct
9 Correct 48 ms 44488 KB Output is correct
10 Correct 99 ms 52680 KB Output is correct
11 Correct 87 ms 29904 KB Output is correct
12 Correct 120 ms 84400 KB Output is correct
13 Correct 129 ms 85688 KB Output is correct
14 Correct 102 ms 53144 KB Output is correct
15 Correct 57 ms 35692 KB Output is correct
16 Correct 31 ms 29464 KB Output is correct
17 Correct 73 ms 45900 KB Output is correct
18 Correct 25 ms 32916 KB Output is correct
19 Correct 209 ms 83676 KB Output is correct
20 Correct 202 ms 92928 KB Output is correct
21 Correct 44 ms 42832 KB Output is correct
22 Correct 70 ms 50696 KB Output is correct
23 Correct 292 ms 96160 KB Output is correct
24 Correct 180 ms 64928 KB Output is correct
25 Correct 106 ms 52192 KB Output is correct
26 Correct 344 ms 88092 KB Output is correct
27 Correct 303 ms 84148 KB Output is correct
28 Correct 20 ms 30808 KB Output is correct
29 Correct 415 ms 79732 KB Output is correct
30 Correct 440 ms 83320 KB Output is correct
31 Correct 346 ms 82980 KB Output is correct
32 Correct 106 ms 30544 KB Output is correct
33 Correct 330 ms 83668 KB Output is correct