Submission #909349

#	Time	Username	Problem	Language	Result	Execution time	Memory
909349		12345678	Rigged Roads (NOI19_riggedroads)	C++17	27 / 100	242 ms	53124 KiB

riggedroads

#include <bits/stdc++.h>

using namespace std;

const int nx=3e5+5, kx=19;

int n, m, x, t[nx], dp[nx], cnt, ans[nx], used[nx];
vector<int> vl[nx];
vector<pair<int, int>> ed(nx), d[nx];

void dfs(int u, int p, int idx)
{
    for (auto [v, w]:d[u]) if (v!=p) dfs(v, u, w), dp[u]=min(dp[u], dp[v]);
    if (idx!=-1&&dp[u]<idx) used[idx]=1, vl[dp[u]].push_back(idx);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++) cin>>ed[i].first>>ed[i].second;
    for (int i=1; i<=n; i++) dp[i]=INT_MAX;
    for (int i=1; i<n; i++) cin>>x, t[x]=1, d[ed[x].first].push_back({ed[x].second, x}), d[ed[x].second].push_back({ed[x].first, x});
    for (int i=m; i>=1; i--) if (!t[i]) dp[ed[i].first]=dp[ed[i].second]=i;
    dfs(1, 1, -1);
    for (int i=1; i<=m; i++)
    {
        if (t[i]&&!used[i]) ans[i]=++cnt;
        else if (!t[i])
        {
            sort(vl[i].begin(), vl[i].end());
            for (auto tmp:vl[i]) ans[tmp]=++cnt;
            ans[i]=++cnt;
        }
        //cout<<"val "<<i<<':';
        //for (int j=1; j<=m; j++) cout<<ans[j]<<' ';
        //cout<<'\n';
    }
    for (int i=1; i<=m; i++) cout<<ans[i]<<' ';
}

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