oj.uz

Submission #996665

# Submission time Handle Problem Language Result Execution time Memory
996665 2024-06-11T04:08:37 Z cpptowin Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 208 ms 82300 KB 
#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
#define int long long
#define inf (int)1e18
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1LL)
#define offbit(i,j) (i^(1LL<<j))
#define onbit(i,j) (i|(1LL<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
int n,m;
vii ke[maxn];
pii edge[maxn];
int par[maxn],h[maxn],id[maxn],res[maxn];
int now;
void dfs(int u)
{
    for(auto [v,w] : ke[u]) if(v != par[u])
        {
            id[v] = w;
            par[v] = u;
            h[v] = h[u] + 1;
            dfs(v);
        }
}
struct DSU
{
    vi par;
    DSU(int n) : par(n) {};
    void make(int u)
    {
        par[u] = u;
    }
    int find(int u)
    {
        return u == par[u] ? u : par[u] = find(par[u]);
    }
    void Union(int u,int v)
    {
        u = find(u);
        par[v] = u;
    }
};
main()
{
#define name "TASK"
    if(fopen(name".inp","r"))
    {
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    fo(i,1,m) cin >> edge[i].fi >> edge[i].se;
    fo(i,1,n - 1)
    {
        int x;
        cin >> x;
        auto [u,v] = edge[x];
        ke[u].pb(v,x);
        ke[v].pb(u,x);
    }
    dfs(1);
    DSU g(n + 5);
    fo(i,1,n) g.make(i);
    fo(i,1,m)
    {
        if(res[i]) continue;
        auto [u,v] = edge[i];
        u = g.find(u);
        v = g.find(v);
        vi save;
        while(u != v)
        {
            if(h[u] < h[v]) swap(u,v);
            save.pb(id[u]);
            g.Union(par[u],u);
            u = g.find(u);
        }
//        cout << i;en;
//        for(int it : save) cout << it << ' ';en;
        sort(save.begin(),save.end());
        for(auto it : save) res[it] = ++now;
        if(!res[i]) res[i] = ++now;
    }
    fo(i,1,m) cout << res[i] << ' ';
}

Compilation message

riggedroads.cpp:71:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   71 | main()
      | ^~~~
riggedroads.cpp: In function 'int main()':
riggedroads.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
19.0 / 19.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 42796 KB Output is correct
2 Correct 68 ms 50776 KB Output is correct
3 Correct 56 ms 42188 KB Output is correct
4 Correct 101 ms 66488 KB Output is correct
5 Correct 99 ms 69916 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 53300 KB Output is correct
2 Correct 47 ms 41092 KB Output is correct
3 Correct 19 ms 35460 KB Output is correct
4 Correct 44 ms 48672 KB Output is correct
5 Correct 21 ms 37088 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 73720 KB Output is correct
2 Correct 147 ms 79236 KB Output is correct
3 Correct 37 ms 44800 KB Output is correct
4 Correct 56 ms 50940 KB Output is correct
5 Correct 173 ms 82300 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 61336 KB Output is correct
2 Correct 64 ms 50400 KB Output is correct
3 Correct 208 ms 75600 KB Output is correct
4 Correct 150 ms 72528 KB Output is correct
5 Correct 21 ms 34392 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29532 KB Output is correct
2 Correct 4 ms 29528 KB Output is correct
3 Correct 4 ms 29532 KB Output is correct
4 Correct 5 ms 29788 KB Output is correct
5 Correct 5 ms 29788 KB Output is correct
6 Correct 6 ms 29788 KB Output is correct
7 Correct 5 ms 29528 KB Output is correct
8 Correct 5 ms 29788 KB Output is correct
9 Correct 37 ms 42796 KB Output is correct
10 Correct 68 ms 50776 KB Output is correct
11 Correct 56 ms 42188 KB Output is correct
12 Correct 101 ms 66488 KB Output is correct
13 Correct 99 ms 69916 KB Output is correct
14 Correct 55 ms 53300 KB Output is correct
15 Correct 47 ms 41092 KB Output is correct
16 Correct 19 ms 35460 KB Output is correct
17 Correct 44 ms 48672 KB Output is correct
18 Correct 21 ms 37088 KB Output is correct
19 Correct 138 ms 73720 KB Output is correct
20 Correct 147 ms 79236 KB Output is correct
21 Correct 37 ms 44800 KB Output is correct
22 Correct 56 ms 50940 KB Output is correct
23 Correct 173 ms 82300 KB Output is correct
24 Correct 101 ms 61336 KB Output is correct
25 Correct 64 ms 50400 KB Output is correct
26 Correct 208 ms 75600 KB Output is correct
27 Correct 150 ms 72528 KB Output is correct
28 Correct 21 ms 34392 KB Output is correct
29 Correct 165 ms 74768 KB Output is correct
30 Correct 161 ms 74380 KB Output is correct
31 Correct 160 ms 69320 KB Output is correct
32 Correct 50 ms 42764 KB Output is correct
33 Correct 172 ms 69992 KB Output is correct