oj.uz

Submission #302278

# Submission time Handle Problem Language Result Execution time Memory
302278 2020-09-18T15:13:03 Z kevlee Simurgh (IOI17_simurgh) C++17
0 / 100
 1 ms 384 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];
int group[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(i, 0, n-1) group[i] = i;
    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;
      }
    }
    query.pb(edges[i][0].se);
    int cnt = count_common_roads(query);
    query.pop_back();
    FOR(j, 1, sz-1) {
      query.pb(edges[i][j].se);
      int cnt2 = count_common_roads(query);
      if (cnt2 > cnt) {
        ans.pb(edges[i][j].se);
        break;
      }
      if (cnt2 < cnt) {
        ans.pb(edges[i][0].se);
        break;
      }
      query.pop_back();
    }
  }
  sort(all(ans));
  auto iter = unique(all(ans));
  ans.resize(distance(ans.begin(), iter));
  for (auto it: ans) cerr << it << ' ' ;
  cerr << endl;
  return ans;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Incorrect 1 ms 384 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Incorrect 1 ms 384 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Incorrect 1 ms 384 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB correct
2 Incorrect 0 ms 384 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Incorrect 1 ms 384 KB WA in grader: NO
3 Halted 0 ms 0 KB -