oj.uz

Submission #593725

# Submission time Handle Problem Language Result Execution time Memory
593725 2022-07-11T14:06:26 Z keta_tsimakuridze Simurgh (IOI17_simurgh) C++17
51 / 100
 179 ms 51088 KB 
#include "simurgh.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int N = 1e6 + 5;
int f[N], t[N], CNT, P[N], h[N], Nn, up[N];
pii mn[N];
vector<int> golden;
vector<pii> V[N], adj[N];
vector<int> edges;
void dfs0(int u, int p) {
    f[u] = 1;
    for(int i = 0; i < V[u].size(); i++) {
        if(V[u][i].f == p) continue;
        if(!f[V[u][i].f]) {
            dfs0(V[u][i].f, u); //cout << "++" << V[u][i].s << endl;
            edges.push_back(V[u][i].s);
            t[V[u][i].s] = 1;
        }
    }
}
int rem(int e1, int e2) {
    vector<int> x;
    for(int i = 0; i < edges.size(); i++) {
        if(e1 != edges[i]) x.push_back(edges[i]);
    }
    x.push_back(e2);
    return count_common_roads(x) - CNT;
}
void add(int a, int b, int x) {
    adj[a].push_back({b, x});
    adj[b].push_back({a, -x});

}
void dfs(int u, int p) {
    mn[u] = {Nn + 1, 0};
    P[u] = p;
    if(u) h[u] = h[p] + 1; //cout << u << endl;
    for(int i = 0; i < V[u].size(); i++) {
        int e = V[u][i].s, v = V[u][i].f;
        if(v == p) continue;
        if(t[e]) {
            up[v] = e;
            dfs(v, u);
            if(mn[v].f > h[u]) golden[e] = 1;
            else add(e, mn[v].s, rem(e, mn[v].s));
            mn[u] = min(mn[u], mn[v]);
        } else if(h[v] < h[u]) {
            int x = u;
            while(P[x] != v) {
                x = P[x];
            }
            add(up[x], e, rem(up[x], e));
            mn[u] = min(mn[u], {h[v], e});
        }
    }
}
std::vector<int> find_roads(int nn, std::vector<int> u, std::vector<int> vv) {
    int m = u.size(); Nn = nn;
    golden.resize(m);
    for(int i = 0; i < m; i++) {
        V[u[i]].push_back({vv[i], i});
        V[vv[i]].push_back({u[i], i});
    }
    dfs0(0, -1); // 0dan iwyeba?
    CNT = count_common_roads(edges);
    dfs(0, -1);
    vector<int> vis(m);
    for(int i = 0; i < m; i++) {
        if(!vis[i]) {
            queue<int> q;
            q.push(i);
            h[i] = 0;
            int mx = 0;
            vector<int> x;
            while(q.size()) {
                int u = q.front(); q.pop();
                mx = max(mx, h[u]);
                for(int j = 0; j < adj[u].size(); j++) {
                    if(vis[adj[u][j].f]) continue;
                    h[adj[u][j].f] = h[u] + adj[u][j].s;
                    vis[adj[u][j].f] = 1;
                    q.push(adj[u][j].f);
                }
                x.push_back(u);
            }
            for(int j = 0; j < x.size(); j++) if(h[x[j]] == mx) golden[x[j]] = 1;
        }
    }
    vector<int> ans;
    for(int i = 0; i < m; i++) {
        if(golden[i]) ans.push_back(i);
    }
    return ans;
}

Compilation message

simurgh.cpp: In function 'void dfs0(int, int)':
simurgh.cpp:15:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
simurgh.cpp: In function 'int rem(int, int)':
simurgh.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i = 0; i < edges.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~
simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:81:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |                 for(int j = 0; j < adj[u].size(); j++) {
      |                                ~~^~~~~~~~~~~~~~~
simurgh.cpp:89:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             for(int j = 0; j < x.size(); j++) if(h[x[j]] == mx) golden[x[j]] = 1;
      |                            ~~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47180 KB correct
2 Correct 23 ms 47224 KB correct
3 Correct 25 ms 47296 KB correct
4 Correct 24 ms 47200 KB correct
5 Correct 23 ms 47232 KB correct
6 Correct 27 ms 47300 KB correct
7 Correct 21 ms 47228 KB correct
8 Correct 22 ms 47316 KB correct
9 Correct 23 ms 47308 KB correct
10 Correct 23 ms 47272 KB correct
11 Correct 28 ms 47316 KB correct
12 Correct 27 ms 47204 KB correct
13 Correct 23 ms 47316 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47180 KB correct
2 Correct 23 ms 47224 KB correct
3 Correct 25 ms 47296 KB correct
4 Correct 24 ms 47200 KB correct
5 Correct 23 ms 47232 KB correct
6 Correct 27 ms 47300 KB correct
7 Correct 21 ms 47228 KB correct
8 Correct 22 ms 47316 KB correct
9 Correct 23 ms 47308 KB correct
10 Correct 23 ms 47272 KB correct
11 Correct 28 ms 47316 KB correct
12 Correct 27 ms 47204 KB correct
13 Correct 23 ms 47316 KB correct
14 Correct 24 ms 47356 KB correct
15 Correct 24 ms 47444 KB correct
16 Correct 26 ms 47400 KB correct
17 Correct 26 ms 47396 KB correct
18 Correct 24 ms 47256 KB correct
19 Correct 24 ms 47444 KB correct
20 Correct 24 ms 47436 KB correct
21 Correct 27 ms 47380 KB correct
22 Correct 30 ms 47308 KB correct
23 Correct 26 ms 47292 KB correct
24 Correct 27 ms 47300 KB correct
25 Correct 30 ms 47204 KB correct
26 Correct 26 ms 47316 KB correct
27 Correct 24 ms 47372 KB correct
28 Correct 25 ms 47276 KB correct
29 Correct 23 ms 47300 KB correct
30 Correct 24 ms 47364 KB correct
31 Correct 25 ms 47276 KB correct
32 Correct 23 ms 47316 KB correct
33 Correct 23 ms 47308 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47180 KB correct
2 Correct 23 ms 47224 KB correct
3 Correct 25 ms 47296 KB correct
4 Correct 24 ms 47200 KB correct
5 Correct 23 ms 47232 KB correct
6 Correct 27 ms 47300 KB correct
7 Correct 21 ms 47228 KB correct
8 Correct 22 ms 47316 KB correct
9 Correct 23 ms 47308 KB correct
10 Correct 23 ms 47272 KB correct
11 Correct 28 ms 47316 KB correct
12 Correct 27 ms 47204 KB correct
13 Correct 23 ms 47316 KB correct
14 Correct 24 ms 47356 KB correct
15 Correct 24 ms 47444 KB correct
16 Correct 26 ms 47400 KB correct
17 Correct 26 ms 47396 KB correct
18 Correct 24 ms 47256 KB correct
19 Correct 24 ms 47444 KB correct
20 Correct 24 ms 47436 KB correct
21 Correct 27 ms 47380 KB correct
22 Correct 30 ms 47308 KB correct
23 Correct 26 ms 47292 KB correct
24 Correct 27 ms 47300 KB correct
25 Correct 30 ms 47204 KB correct
26 Correct 26 ms 47316 KB correct
27 Correct 24 ms 47372 KB correct
28 Correct 25 ms 47276 KB correct
29 Correct 23 ms 47300 KB correct
30 Correct 24 ms 47364 KB correct
31 Correct 25 ms 47276 KB correct
32 Correct 23 ms 47316 KB correct
33 Correct 23 ms 47308 KB correct
34 Correct 176 ms 50336 KB correct
35 Correct 157 ms 50272 KB correct
36 Correct 118 ms 49512 KB correct
37 Correct 29 ms 47372 KB correct
38 Correct 179 ms 50372 KB correct
39 Correct 141 ms 49996 KB correct
40 Correct 115 ms 49540 KB correct
41 Correct 166 ms 50280 KB correct
42 Correct 179 ms 50412 KB correct
43 Correct 96 ms 48972 KB correct
44 Correct 79 ms 48536 KB correct
45 Correct 93 ms 48744 KB correct
46 Correct 83 ms 48468 KB correct
47 Correct 51 ms 47744 KB correct
48 Correct 28 ms 47268 KB correct
49 Correct 29 ms 47432 KB correct
50 Correct 44 ms 47820 KB correct
51 Correct 92 ms 48740 KB correct
52 Correct 88 ms 48616 KB correct
53 Correct 80 ms 48432 KB correct
54 Correct 95 ms 49080 KB correct
55 Correct 92 ms 48844 KB correct
56 Correct 93 ms 48796 KB correct
57 Correct 98 ms 48760 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47252 KB correct
2 Correct 23 ms 47316 KB correct
3 Incorrect 138 ms 51088 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47180 KB correct
2 Correct 23 ms 47224 KB correct
3 Correct 25 ms 47296 KB correct
4 Correct 24 ms 47200 KB correct
5 Correct 23 ms 47232 KB correct
6 Correct 27 ms 47300 KB correct
7 Correct 21 ms 47228 KB correct
8 Correct 22 ms 47316 KB correct
9 Correct 23 ms 47308 KB correct
10 Correct 23 ms 47272 KB correct
11 Correct 28 ms 47316 KB correct
12 Correct 27 ms 47204 KB correct
13 Correct 23 ms 47316 KB correct
14 Correct 24 ms 47356 KB correct
15 Correct 24 ms 47444 KB correct
16 Correct 26 ms 47400 KB correct
17 Correct 26 ms 47396 KB correct
18 Correct 24 ms 47256 KB correct
19 Correct 24 ms 47444 KB correct
20 Correct 24 ms 47436 KB correct
21 Correct 27 ms 47380 KB correct
22 Correct 30 ms 47308 KB correct
23 Correct 26 ms 47292 KB correct
24 Correct 27 ms 47300 KB correct
25 Correct 30 ms 47204 KB correct
26 Correct 26 ms 47316 KB correct
27 Correct 24 ms 47372 KB correct
28 Correct 25 ms 47276 KB correct
29 Correct 23 ms 47300 KB correct
30 Correct 24 ms 47364 KB correct
31 Correct 25 ms 47276 KB correct
32 Correct 23 ms 47316 KB correct
33 Correct 23 ms 47308 KB correct
34 Correct 176 ms 50336 KB correct
35 Correct 157 ms 50272 KB correct
36 Correct 118 ms 49512 KB correct
37 Correct 29 ms 47372 KB correct
38 Correct 179 ms 50372 KB correct
39 Correct 141 ms 49996 KB correct
40 Correct 115 ms 49540 KB correct
41 Correct 166 ms 50280 KB correct
42 Correct 179 ms 50412 KB correct
43 Correct 96 ms 48972 KB correct
44 Correct 79 ms 48536 KB correct
45 Correct 93 ms 48744 KB correct
46 Correct 83 ms 48468 KB correct
47 Correct 51 ms 47744 KB correct
48 Correct 28 ms 47268 KB correct
49 Correct 29 ms 47432 KB correct
50 Correct 44 ms 47820 KB correct
51 Correct 92 ms 48740 KB correct
52 Correct 88 ms 48616 KB correct
53 Correct 80 ms 48432 KB correct
54 Correct 95 ms 49080 KB correct
55 Correct 92 ms 48844 KB correct
56 Correct 93 ms 48796 KB correct
57 Correct 98 ms 48760 KB correct
58 Correct 24 ms 47252 KB correct
59 Correct 23 ms 47316 KB correct
60 Incorrect 138 ms 51088 KB WA in grader: NO
61 Halted 0 ms 0 KB -