oj.uz

Submission #909349

# Submission time Handle Problem Language Result Execution time Memory
909349 2024-01-17T07:28:53 Z 12345678 Rigged Roads (NOI19_riggedroads) C++17
27 / 100
 242 ms 53124 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 21340 KB Output is correct
2 Correct 6 ms 21340 KB Output is correct
3 Correct 6 ms 21336 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 21340 KB Output is correct
2 Correct 6 ms 21340 KB Output is correct
3 Correct 6 ms 21336 KB Output is correct
4 Correct 7 ms 21340 KB Output is correct
5 Incorrect 7 ms 21420 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 27452 KB Output is correct
2 Correct 65 ms 31172 KB Output is correct
3 Correct 64 ms 27384 KB Output is correct
4 Correct 108 ms 39564 KB Output is correct
5 Correct 105 ms 39232 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 36528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 46804 KB Output is correct
2 Correct 242 ms 53124 KB Output is correct
3 Correct 41 ms 30212 KB Output is correct
4 Correct 54 ms 34384 KB Output is correct
5 Correct 234 ms 51916 KB Output is correct

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 40508 KB Output is correct
2 Incorrect 73 ms 35000 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 21340 KB Output is correct
2 Correct 6 ms 21340 KB Output is correct
3 Correct 6 ms 21336 KB Output is correct
4 Correct 7 ms 21340 KB Output is correct
5 Incorrect 7 ms 21420 KB Output isn't correct
6 Halted 0 ms 0 KB -