oj.uz

Submission #302681

# Submission time Handle Problem Language Result Execution time Memory
302681 2020-09-19T03:36:41 Z kevlee Simurgh (IOI17_simurgh) C++17
30 / 100
 256 ms 4004 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
#define h1 7897897897897897
#define h2 7897466719774591
#define b1 98762051
#define b2 98765431
#define inf 1000000000
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a))
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
vi ans;
int m;
vp edges[505];
vi nodes[505];
int group[505];
bool used[505];
int f(int x) {
  return x == group[x] ? x : group[x] = f(group[x]);
}
vi find_roads(int n, vi u, vi v) {
  m = u.size();
  FOR(i, 0, m-1) {
    edges[u[i]].emplace_back(v[i], i);
    edges[v[i]].emplace_back(u[i], i);
  }
  FOR(i, 0, n-1) {
    int sz = edges[i].size();
    if (sz == 1) {
      ans.pb(edges[i][0].se);
      continue;
    }
    FOR(j, 0, n-1) group[j] = j;
    vi query;
    FOR(j, 0, m-1) {
      if (u[j] == i || v[j] == i) continue;
      int x = f(u[j]);
      int y = f(v[j]);
      if (x != y) {
        query.pb(j);
        group[x] = y;
      }
    }
    FOR(j, 0, n-1) nodes[j].clear();
    FOR(j, 0, edges[i].size() - 1) {
      nodes[f(edges[i][j].fi)].pb(edges[i][j].fi);
    }
    FOR(k, 0, n-1) {
      //cout << i <<"  "<<k << "  " << nodes[k].size() << endl; 
      if (nodes[k].size() == 0 || k == i) continue;
      vp res;
      vi ask = query;
      FOR(j, 0, n-1) used[j] = false;
      used[k] = used[i] = true;
      vi candidate;
      FOR(j, 0, edges[i].size() - 1) {
        int x = f(edges[i][j].fi);
        if (!used[x]) {
          used[x] = true;
          ask.pb(edges[i][j].se);
        } else if (x == k) {
          candidate.pb(edges[i][j].se);
        }
      }

      for (auto it: candidate) {
        ask.pb(it);
        //for (auto q: ask) cout << q <<' ';
        //cout << endl;
        int cnt = count_common_roads(ask);
        res.pb({cnt, it});
        ask.pop_back();
      }
    
      sort(res.rbegin(), res.rend());
      for (auto p: res) {
        if (p.fi != res[0].fi) {
          break;
        }
        ans.pb(p.se);
      }
    }
  }
  sort(all(ans));
  auto iter = unique(all(ans));
  ans.resize(distance(ans.begin(), iter));
  //for (auto it: ans) cout << it << ' ' ;
  //cout << endl;
  return ans;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:23:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 | #define FOR(i, a, b) for (int i = (a); i <= (b); i++)
      |                                          ^
simurgh.cpp:58:5: note: in expansion of macro 'FOR'
   58 |     FOR(j, 0, edges[i].size() - 1) {
      |     ^~~
simurgh.cpp:23:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 | #define FOR(i, a, b) for (int i = (a); i <= (b); i++)
      |                                          ^
simurgh.cpp:69:7: note: in expansion of macro 'FOR'
   69 |       FOR(j, 0, edges[i].size() - 1) {
      |       ^~~

Subtask #1
13.0 / 13.0

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

Subtask #3
0 / 21.0

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