oj.uz

Submission #293065

# Submission time Handle Problem Language Result Execution time Memory
293065 2020-09-07T15:54:56 Z Kastanda Simurgh (IOI17_simurgh) C++11
30 / 100
 676 ms 7932 KB 
// M
#include<bits/stdc++.h>
#include "simurgh.h"
using namespace std;
const int N = 505, MXM = N * N / 2;
int n, m, A[MXM], B[MXM];
bool Del[MXM];
int P[N], M[N], MR[N], PE[N];
vector < int > Tre, Cyc;
vector < pair < int , int > > Adj[N];
void DFS(int v, int p, int pe)
{
        M[v] = 1;
        P[v] = p;
        PE[v] = pe;
        for (auto e : Adj[v])
        {
                int u = e.first;
                int id = e.second;
                if (id == pe || Del[id])
                        continue;
                if (!M[u])
                        DFS(u, v, id);
                else if (M[u] == 1 && !Cyc.size())
                {
                        int nw = v;
                        while (nw != u)
                                Cyc.push_back(PE[nw]), MR[nw] = 1, nw = P[nw];
                        Cyc.push_back(id);
                }
        }
        if (!MR[v] && pe != -1)
                Tre.push_back(pe);
        M[v] = 2;
}

vector < int > find_roads(int _n, vector < int > _u, vector < int > _v)
{
        n = _n;
        m = (int)_u.size();
        for (int i = 0; i < m; i ++)
                A[i] = _u[i], B[i] = _v[i];

        for (int i = 0; i < m; i ++)
        {
                Adj[A[i]].push_back({B[i], i});
                Adj[B[i]].push_back({A[i], i});
        }
        assert(m <= 3e4);

        while (true)
        {
                Tre.clear();
                Cyc.clear();
                memset(M, 0, sizeof(M));
                memset(MR, 0, sizeof(MR));
                DFS(0, -1, -1);
                if (!Cyc.size())
                        break;
                vector < int > Val(n + 1, -1);
                assert(Cyc.size() >= 3);
                int mx = -1;
                for (int i = 0; i < (int)Cyc.size(); i ++)
                {
                        vector < int > tmp = Tre;
                        for (int j = 0; j < (int)Cyc.size(); j ++)
                                if (i != j)
                                        tmp.push_back(Cyc[j]);
                        assert(tmp.size() == n - 1);
                        Val[i] = count_common_roads(tmp);

                        /*printf("Asking :: %d || ", Val[i]);
                        for (int j : tmp)
                                printf("%d ", j);
                        printf("\n");*/

                        //mn = min(mn, Val[i]);
                        mx = max(mx, Val[i]);
                }
                for (int i = 0; i < (int)Cyc.size(); i ++)
                        if (Val[i] == mx)
                                Del[Cyc[i]] = 1;
        }
        vector < int > vec;
        for (int i = 0; i < m; i ++)
                if (Del[i] == 0)
                        vec.push_back(i);
        assert(vec.size() == n - 1);
        return vec;
}

Compilation message

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:69:43: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |                         assert(tmp.size() == n - 1);
      |                                ~~~~~~~~~~~^~~~~~~~
simurgh.cpp:88:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   88 |         assert(vec.size() == n - 1);
      |                ~~~~~~~~~~~^~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 0 ms 384 KB correct
5 Correct 1 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 0 ms 384 KB correct
8 Correct 0 ms 384 KB correct
9 Correct 0 ms 384 KB correct
10 Correct 0 ms 384 KB correct
11 Correct 1 ms 384 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 0 ms 384 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 0 ms 384 KB correct
5 Correct 1 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 0 ms 384 KB correct
8 Correct 0 ms 384 KB correct
9 Correct 0 ms 384 KB correct
10 Correct 0 ms 384 KB correct
11 Correct 1 ms 384 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 0 ms 384 KB correct
14 Correct 10 ms 384 KB correct
15 Correct 12 ms 384 KB correct
16 Correct 10 ms 384 KB correct
17 Correct 7 ms 464 KB correct
18 Correct 2 ms 384 KB correct
19 Correct 7 ms 384 KB correct
20 Correct 7 ms 384 KB correct
21 Correct 6 ms 384 KB correct
22 Correct 6 ms 384 KB correct
23 Correct 7 ms 384 KB correct
24 Correct 7 ms 384 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 8 ms 448 KB correct
27 Correct 7 ms 384 KB correct
28 Correct 3 ms 384 KB correct
29 Correct 1 ms 512 KB correct
30 Correct 6 ms 384 KB correct
31 Correct 9 ms 384 KB correct
32 Correct 8 ms 384 KB correct
33 Correct 6 ms 384 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 0 ms 384 KB correct
5 Correct 1 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 0 ms 384 KB correct
8 Correct 0 ms 384 KB correct
9 Correct 0 ms 384 KB correct
10 Correct 0 ms 384 KB correct
11 Correct 1 ms 384 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 0 ms 384 KB correct
14 Correct 10 ms 384 KB correct
15 Correct 12 ms 384 KB correct
16 Correct 10 ms 384 KB correct
17 Correct 7 ms 464 KB correct
18 Correct 2 ms 384 KB correct
19 Correct 7 ms 384 KB correct
20 Correct 7 ms 384 KB correct
21 Correct 6 ms 384 KB correct
22 Correct 6 ms 384 KB correct
23 Correct 7 ms 384 KB correct
24 Correct 7 ms 384 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 8 ms 448 KB correct
27 Correct 7 ms 384 KB correct
28 Correct 3 ms 384 KB correct
29 Correct 1 ms 512 KB correct
30 Correct 6 ms 384 KB correct
31 Correct 9 ms 384 KB correct
32 Correct 8 ms 384 KB correct
33 Correct 6 ms 384 KB correct
34 Incorrect 676 ms 2168 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 384 KB correct
3 Runtime error 29 ms 7932 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 0 ms 384 KB correct
5 Correct 1 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 0 ms 384 KB correct
8 Correct 0 ms 384 KB correct
9 Correct 0 ms 384 KB correct
10 Correct 0 ms 384 KB correct
11 Correct 1 ms 384 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 0 ms 384 KB correct
14 Correct 10 ms 384 KB correct
15 Correct 12 ms 384 KB correct
16 Correct 10 ms 384 KB correct
17 Correct 7 ms 464 KB correct
18 Correct 2 ms 384 KB correct
19 Correct 7 ms 384 KB correct
20 Correct 7 ms 384 KB correct
21 Correct 6 ms 384 KB correct
22 Correct 6 ms 384 KB correct
23 Correct 7 ms 384 KB correct
24 Correct 7 ms 384 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 8 ms 448 KB correct
27 Correct 7 ms 384 KB correct
28 Correct 3 ms 384 KB correct
29 Correct 1 ms 512 KB correct
30 Correct 6 ms 384 KB correct
31 Correct 9 ms 384 KB correct
32 Correct 8 ms 384 KB correct
33 Correct 6 ms 384 KB correct
34 Incorrect 676 ms 2168 KB WA in grader: NO
35 Halted 0 ms 0 KB -