oj.uz

Submission #293078

# Submission time Handle Problem Language Result Execution time Memory
293078 2020-09-07T16:01:29 Z Kastanda Simurgh (IOI17_simurgh) C++11
0 / 100
 28 ms 7804 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], Sure[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 (Sure[id] && !M[u])
                        DFS(u, v, id);
        }
        for (auto e : Adj[v])
        {
                int u = e.first;
                int id = e.second;
                if (id == pe || Del[id])
                        continue;
                if (Sure[id])
                        continue;
                if (!M[u])
                        DFS(u, v, id);
                else if (M[u] == 1 && !Cyc.size())
                {
                        int nw = v;
                        while (nw != u)
                        {
                                if (!Sure[PE[nw]])
                                        Cyc.push_back(PE[nw]);
                                MR[nw] = 1;
                                nw = P[nw];
                        }
                        Cyc.push_back(id);
                }
        }
        if (pe != -1 && (!MR[v] || Sure[pe]))
                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);
                int mx = -1, mn = n;
                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;
                if (mn < mx)
                {
                        for (int i = 0; i < (int)Cyc.size(); i ++)
                                if (Val[i] == mn)
                                        Sure[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:84:43: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |                         assert(tmp.size() == n - 1);
      |                                ~~~~~~~~~~~^~~~~~~~
simurgh.cpp:109:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |         assert(vec.size() == n - 1);
      |                ~~~~~~~~~~~^~~~~~~~

Subtask #1
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 0 ms 384 KB correct
4 Correct 1 ms 384 KB correct
5 Correct 1 ms 384 KB correct
6 Runtime error 1 ms 512 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #2
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 0 ms 384 KB correct
4 Correct 1 ms 384 KB correct
5 Correct 1 ms 384 KB correct
6 Runtime error 1 ms 512 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

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 0 ms 384 KB correct
4 Correct 1 ms 384 KB correct
5 Correct 1 ms 384 KB correct
6 Runtime error 1 ms 512 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB correct
2 Correct 0 ms 384 KB correct
3 Runtime error 28 ms 7804 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 0 ms 384 KB correct
4 Correct 1 ms 384 KB correct
5 Correct 1 ms 384 KB correct
6 Runtime error 1 ms 512 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -