oj.uz

Submission #375602

# Submission time Handle Problem Language Result Execution time Memory
375602 2021-03-09T15:05:39 Z Mamnoon_Siam Simurgh (IOI17_simurgh) C++17
30 / 100
 291 ms 5612 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
#define sz(v) (int)(v).size()
#define all(v) begin(v), end(v)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int N = 1 << 8;
using bs = bitset<N>;

bs g[N], unvis, onstk;
int eid[N][N], n;
bool flag; // have I detected a cyc yet?
int par[N];
bool oncyc[N*N];
vi U, V;

void discard(int u, int v) {
  eid[u][v] = eid[v][u] = -1;
  g[u][v] = g[v][u] = 0;
}

void dfs(int u, int dad, vi& cyc, vi& tr) {
  unvis[u] = 0;
  onstk[u] = 1;
  if(!flag) {
    if(~dad) onstk[dad] = 0;
    int back = (int)(g[u] & onstk)._Find_first();
    if(back < n) {
      flag = 1;
      cyc.emplace_back(eid[back][u]);
      int v = u;
      while(v != back) {
        cyc.emplace_back(eid[par[v]][v]);
        v = par[v];
      }
    }
    if(~dad) onstk[dad] = 1;
  }
  while(true) {
    int v = (int)(g[u] & unvis)._Find_first();
    if(v >= n) break;
    par[v] = u;
    tr.emplace_back(eid[u][v]);
    dfs(v, u, cyc, tr);
  }
  onstk[u] = 0;
}

vi find_roads(int _n, vi _U, vi _V) {
  n = _n, U = _U, V = _V;
  for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) eid[i][j] = -1;
  for(int i = 0; i < sz(U); ++i) {
    int u = U[i], v = V[i];
    eid[u][v] = eid[v][u] = i;
    g[u][v] = g[v][u] = 1;
  }
  
  while(true) {
    unvis.set();
    onstk.reset();
    flag = 0;
    vi cyc, tr;
    dfs(0, -1, cyc, tr);
    if(!flag) break;
    debug(tr);
    debug(cyc);
    for(int i : cyc) oncyc[i] = 1;
    vi r; r.reserve(n);
    for(int i : cyc) r.pb(i);
    for(int i : tr) if(!oncyc[i]) r.pb(i);

    vi rep(sz(cyc));
    int del_v = INT_MIN;
    for(int i = 0; i < sz(cyc); ++i) {
      vi rr = r;
      rr.erase(find(all(rr), cyc[i]));
      debug(rr);
      rep[i] = count_common_roads(rr);
      del_v = max(del_v, rep[i]);
    }
    for(int i = 0; i < sz(cyc); ++i) {
      if(rep[i] == del_v) {
        debug(cyc[i]);
        discard(U[cyc[i]], V[cyc[i]]);
      }
    }
    for(int i : cyc) oncyc[i] = 0;
  }

  set<int> rem_edges;
  for(int i = 0; i < n; ++i)
    for(int j = 0; j < n; ++j)
      if(~eid[i][j]) rem_edges.insert(eid[i][j]);

  return vi(all(rem_edges));

	/*vi r(n - 1);
	for(int i = 0; i < n - 1; i++)
		r[i] = i;
	int common = count_common_roads(r);
	if(common == n - 1)
		return r;
	r[0] = n - 1;
	return r;*/
  return {};
}

Compilation message

simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:58:20: warning: statement has no effect [-Wunused-value]
   58 | #define debug(...) 42
      |                    ^~
simurgh.cpp:119:5: note: in expansion of macro 'debug'
  119 |     debug(tr);
      |     ^~~~~
simurgh.cpp:58:20: warning: statement has no effect [-Wunused-value]
   58 | #define debug(...) 42
      |                    ^~
simurgh.cpp:120:5: note: in expansion of macro 'debug'
  120 |     debug(cyc);
      |     ^~~~~
simurgh.cpp:58:20: warning: statement has no effect [-Wunused-value]
   58 | #define debug(...) 42
      |                    ^~
simurgh.cpp:131:7: note: in expansion of macro 'debug'
  131 |       debug(rr);
      |       ^~~~~
simurgh.cpp:58:20: warning: statement has no effect [-Wunused-value]
   58 | #define debug(...) 42
      |                    ^~
simurgh.cpp:137:9: note: in expansion of macro 'debug'
  137 |         debug(cyc[i]);
      |         ^~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 6 ms 364 KB correct
15 Correct 9 ms 364 KB correct
16 Correct 9 ms 364 KB correct
17 Correct 5 ms 364 KB correct
18 Correct 3 ms 364 KB correct
19 Correct 5 ms 364 KB correct
20 Correct 7 ms 364 KB correct
21 Correct 4 ms 364 KB correct
22 Correct 4 ms 364 KB correct
23 Correct 4 ms 364 KB correct
24 Correct 3 ms 364 KB correct
25 Correct 1 ms 364 KB correct
26 Correct 4 ms 364 KB correct
27 Correct 4 ms 364 KB correct
28 Correct 2 ms 364 KB correct
29 Correct 1 ms 364 KB correct
30 Correct 3 ms 364 KB correct
31 Correct 4 ms 492 KB correct
32 Correct 5 ms 364 KB correct
33 Correct 4 ms 364 KB correct
34 Incorrect 291 ms 1516 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 364 KB correct
2 Correct 1 ms 364 KB correct
3 Runtime error 24 ms 5612 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 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 6 ms 364 KB correct
15 Correct 9 ms 364 KB correct
16 Correct 9 ms 364 KB correct
17 Correct 5 ms 364 KB correct
18 Correct 3 ms 364 KB correct
19 Correct 5 ms 364 KB correct
20 Correct 7 ms 364 KB correct
21 Correct 4 ms 364 KB correct
22 Correct 4 ms 364 KB correct
23 Correct 4 ms 364 KB correct
24 Correct 3 ms 364 KB correct
25 Correct 1 ms 364 KB correct
26 Correct 4 ms 364 KB correct
27 Correct 4 ms 364 KB correct
28 Correct 2 ms 364 KB correct
29 Correct 1 ms 364 KB correct
30 Correct 3 ms 364 KB correct
31 Correct 4 ms 492 KB correct
32 Correct 5 ms 364 KB correct
33 Correct 4 ms 364 KB correct
34 Incorrect 291 ms 1516 KB WA in grader: NO
35 Halted 0 ms 0 KB -