oj.uz

Submission #37746

# Submission time Handle Problem Language Result Execution time Memory
37746 2017-12-27T13:52:33 Z funcsr Amusement Park (JOI17_amusement_park) C++14
10 / 100
 341 ms 262144 KB 
#include "Joi.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <functional>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
struct UF {
  int N;
  vector<int> U, R;
  UF(int N) : N(N), U(N), R(N, 1) {
    rep(i, N) U[i] = i;
  }
  int find(int x) {
    if (U[x] == x) return x;
    return U[x] = find(U[x]);
  }
  void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (R[x] < R[y]) swap(x, y);
    U[y] = x;
    R[x] += R[y];
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

void Joi(int N, int M, int GA[], int GB[], long long X, int T) {
  int A[10000] = {};
  vector<int> G[10000];
  int deg[10000] = {};
  set<int> S[10000], leaf[10000];
  UF uf(N);
  rep(i, M) {
    int a = GA[i], b = GB[i];
    if (!uf.same(a, b)) {
      G[a].pb(b), G[b].pb(a);
      uf.unite(a, b);
    }
  }
  rep(i, N) A[i] = -1;
  set<int> used, lf;
  queue<P> q;
  q.push(P(0, -1));
  rep(i, 60) {
    int x = q.front()._1, p = q.front()._2; q.pop();
    A[x] = i;
    used.insert(x);
    if (p != -1) deg[x]++, deg[p]++;
    for (int t : G[x]) if (t != p) q.push(P(t, x));
  }
  rep(i, N) if (deg[i] == 1) lf.insert(i);
  for (int x : used) S[x] = used, leaf[x] = lf;

  while (!q.empty()) {
    int x = q.front()._1, p = q.front()._2; q.pop();
    S[x] = set<int>(S[p]);
    S[x].insert(x);
    leaf[x] = set<int>(leaf[p]);
    if (leaf[x].find(p) != leaf[x].end()) leaf[x].erase(p);
    //assert(!leaf[x].empty());
    int from = *leaf[x].begin();
    leaf[x].erase(from);
    S[x].erase(from);
    int ch = -1;
    for (int x : G[from]) if (S[x].find(x) != S[x].end()) ch = x;
    int deg = 0;
    for (int t : G[ch]) if (S[x].find(t) != S[x].end()) deg++;
    if (deg == 1) leaf[x].insert(ch);
    A[x] = A[from];
    leaf[x].insert(x);
    for (int t : G[x]) if (t != p) q.push(P(t, x));
  }
  //rep(i, N) assert(S[i].size() == 60);
  rep(i, N) MessageBoard(i, (X>>A[i])&1);
}

#include "Ioi.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <functional>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
struct UF {
  int N;
  vector<int> U, R;
  UF(int N) : N(N), U(N), R(N, 1) {
    rep(i, N) U[i] = i;
  }
  int find(int x) {
    if (U[x] == x) return x;
    return U[x] = find(U[x]);
  }
  void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (R[x] < R[y]) swap(x, y);
    U[y] = x;
    R[x] += R[y];
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

long long Ioi(int N, int M, int GA[], int GB[], int start, int V, int T) {
  int A[10000] = {};
  vector<int> G[10000];
  int deg[10000] = {};
  set<int> S[10000], leaf[10000];
  UF uf(N);
  rep(i, M) {
    int a = GA[i], b = GB[i];
    if (!uf.same(a, b)) {
      G[a].pb(b), G[b].pb(a);
      uf.unite(a, b);
    }
  }
  rep(i, N) A[i] = -1;
  set<int> used, lf;
  queue<P> q;
  q.push(P(0, -1));
  rep(i, 60) {
    int x = q.front()._1, p = q.front()._2; q.pop();
    A[x] = i;
    used.insert(x);
    if (p != -1) deg[x]++, deg[p]++;
    for (int t : G[x]) if (t != p) q.push(P(t, x));
  }
  rep(i, N) if (deg[i] == 1) lf.insert(i);
  for (int x : used) S[x] = used, leaf[x] = lf;

  while (!q.empty()) {
    int x = q.front()._1, p = q.front()._2; q.pop();
    S[x] = set<int>(S[p]);
    S[x].insert(x);
    leaf[x] = set<int>(leaf[p]);
    if (leaf[x].find(p) != leaf[x].end()) leaf[x].erase(p);
    //assert(!leaf[x].empty());
    int from = *leaf[x].begin();
    leaf[x].erase(from);
    S[x].erase(from);
    int ch = -1;
    for (int x : G[from]) if (S[x].find(x) != S[x].end()) ch = x;
    int deg = 0;
    for (int t : G[ch]) if (S[x].find(t) != S[x].end()) deg++;
    if (deg == 1) leaf[x].insert(ch);
    A[x] = A[from];
    leaf[x].insert(x);
    for (int t : G[x]) if (t != p) q.push(P(t, x));
  }
  //rep(i, N) assert(S[i].size() == 60);
  long long X = 0;
  function<void(int, int, int)> dfs = [&](int x, int p, int v) {
    X |= ((long long)v<<A[x]);
    for (int t : G[x]) if (t != p && S[start].find(t) != S[start].end()) {
      dfs(t, x, Move(t));
      Move(x);
    }
  };
  dfs(start, -1, V);
  return X;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7552 KB Output is correct
2 Correct 0 ms 8344 KB Output is correct
3 Correct 6 ms 9924 KB Output is correct
4 Incorrect 0 ms 7816 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 77556 KB Output is correct
2 Correct 262 ms 88388 KB Output is correct
3 Correct 248 ms 79140 KB Output is correct
4 Correct 341 ms 91020 KB Output is correct
5 Memory limit exceeded 273 ms 262144 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7556 KB Output is correct
2 Correct 0 ms 7548 KB Output is correct
3 Correct 0 ms 7548 KB Output is correct
4 Correct 16 ms 16528 KB Output is correct
5 Correct 22 ms 16532 KB Output is correct
6 Correct 6 ms 16528 KB Output is correct
7 Correct 15 ms 16532 KB Output is correct
8 Correct 22 ms 16532 KB Output is correct
9 Correct 162 ms 65144 KB Output is correct
10 Correct 155 ms 65144 KB Output is correct
11 Correct 164 ms 65140 KB Output is correct
12 Correct 0 ms 7556 KB Output is correct
13 Correct 0 ms 7548 KB Output is correct
14 Correct 0 ms 7288 KB Output is correct
15 Correct 0 ms 7288 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 75448 KB Output is correct
2 Correct 229 ms 81784 KB Output is correct
3 Partially correct 266 ms 100268 KB Partially correct
4 Correct 302 ms 89432 KB Output is correct
5 Memory limit exceeded 269 ms 262144 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 255 ms 97624 KB Output isn't correct
2 Halted 0 ms 0 KB -