Submission #242841

#	Time	Username	Problem	Language	Result	Execution time	Memory
242841		gs18115	Rigged Roads (NOI19_riggedroads)	C++14	100 / 100	518 ms	62408 KiB

riggedroads

#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
int spa[300010][18],dp[300010];
inline int lca(int x,int y)
{
    if(dp[x]<dp[y])
        swap(x,y);
    for(int i=dp[x]-dp[y];i>0;i^=i&-i)
        x=spa[x][__builtin_ctz(i)];
    if(x==y)
        return x;
    for(int i=18;i-->0;)
        if(spa[x][i]!=spa[y][i])
            x=spa[x][i],y=spa[y][i];
    return spa[x][0];
}
vector<pi>adj[300010];
int paw[300010];
void dfs(int x,int p)
{
    dp[x]=dp[p]+1;
    spa[x][0]=p;
    for(int i=0;i<17;i++)
        spa[x][i+1]=spa[spa[x][i]][i];
    for(pi&t:adj[x])
        if(t.fi!=p)
            paw[t.fi]=t.se,dfs(t.fi,x);
    return;
}
int u[300010],v[300010];
bool inl[300010],used[300010];
int pa[300010],ans[300010];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,e;
    cin>>n>>e;
    for(int i=0;i++<e;)
        cin>>u[i]>>v[i];
    vector<int>lst(n-1);
    for(int&t:lst)
    {
        cin>>t;
        adj[u[t]].eb(v[t],t);
        adj[v[t]].eb(u[t],t);
        inl[t]=1;
    }
    paw[1]=inf;
    dfs(1,0);
    int ccn=0;
    used[1]=1;
    for(int i=1;i++<n;)
        pa[i]=spa[i][0];
    for(int i=0;i++<e;)
    {
        if(inl[i])
        {
            if(ans[i]==0)
                ans[i]=++ccn,used[dp[u[i]]>dp[v[i]]?u[i]:v[i]]=1;
            continue;
        }
        vector<int>ls;
        int l=lca(u[i],v[i]);
        int cu,cv;
        for(cu=u[i];dp[cu]>dp[l];cu=pa[cu])
            if(!used[cu])
                ls.eb(paw[cu]),used[cu]=1;
        for(cv=u[i];dp[cv]>dp[cu];)
        {
            int nxt=pa[cv];
            pa[cv]=cu;
            cv=nxt;
        }
        for(cu=v[i];dp[cu]>dp[l];cu=pa[cu])
            if(!used[cu])
                ls.eb(paw[cu]),used[cu]=1;
        for(cv=v[i];dp[cv]>dp[cu];)
        {
            int nxt=pa[cv];
            pa[cv]=cu;
            cv=nxt;
        }
        sort(all(ls));
        for(int&t:ls)
            ans[t]=++ccn;
        ans[i]=++ccn;
    }
    for(int i=0;i++<e;)
        cout<<ans[i]<<' ';
    cout<<endl;
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32