oj.uz

Submission #52516

# Submission time Handle Problem Language Result Execution time Memory
52516 2018-06-26T06:28:16 Z BrunoPloumhans Amusement Park (JOI17_amusement_park) C++14
10 / 100
 34 ms 9040 KB 
#include "Joi.h"

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct UnionFind {
  vector<int> p, ranks;

  UnionFind(int n) : p(n), ranks(n, 0) {
    for(int i = 0; i < n; ++i) {
      p[i] = i;
    }
  }

  int find_set(int a) {
    return p[a] == a ? a : p[a] = find_set(p[a]);
  }

  bool is_same_set(int a, int b) {
    return find_set(a) == find_set(b);
  }

  void unite(int a, int b) {
    int x = find_set(a), y = find_set(b);
    if(x != y) {
      if(ranks[x] > ranks[y])
	p[y] = x;
      else {
	p[x] = y;
	if(ranks[x] == ranks[y]) {
	  ++ranks[y];
	}
      }
    }
  }
};

static vector<vector<int>> adj;
static int tim;
static vector<int> ts;
static vector<int> path;

static void dfs(int u) {
  ts[u] = tim++;
  path.push_back(u);
  for(int v : adj[u]) {
    if(ts[v] == -1) {
      dfs(v);
      path.push_back(u);
    }
  }
}

static void find_tree(int n, int m, signed A[], signed B[]) {
  adj.assign(n, vector<int>());
  path.clear();
  tim = 0;
  UnionFind uf(n);
  vector<pair<int, int>> edges(m);
  for(int i = 0; i < m; ++i) {
    edges[i] = {A[i], B[i]};
  }
  int k = 0;
  for(pair<int, int> p : edges) {
    int u = p.first, v = p.second;
    if(!uf.is_same_set(u, v)) {
      uf.unite(u, v);
      adj[u].push_back(v);
      adj[v].push_back(u);
      ++k;
    }
  }

  assert(k == n-1);

  ts.assign(n, -1);
  dfs(0);
  /*cout << "ts: { ";
  for(int i = 0; i < n; ++i) {
    cout << ts[i] << ", ";
  }
  cout << "}\n";
  cout << "path: { ";
  for(int i : path) {
    cout << i << ", ";
  }
  cout << "}" << endl;*/
}

void Joi(signed n, signed m, signed A[], signed B[], long long X, signed T) {
  int seq[60];
  //cout << "seq: { ";
  for(int i = 0; i < 60; ++i) {
    seq[i] = ((X&(1LL << i)) > 0);
    //cout << seq[i] << ", ";
  }
  //cout << "}" << endl;
  find_tree(n, m, A, B);
  for(int i = 0; i < n; ++i) {
    assert(ts[i] != -1);
    MessageBoard(i, seq[ts[i]%60]);
  }
}

#include "Ioi.h"

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct UnionFind {
  vector<int> p, ranks;

  UnionFind(int n) : p(n), ranks(n, 0) {
    for(int i = 0; i < n; ++i) {
      p[i] = i;
    }
  }

  int find_set(int a) {
    return p[a] == a ? a : p[a] = find_set(p[a]);
  }

  bool is_same_set(int a, int b) {
    return find_set(a) == find_set(b);
  }

  void unite(int a, int b) {
    int x = find_set(a), y = find_set(b);
    if(x != y) {
      if(ranks[x] > ranks[y])
	p[y] = x;
      else {
	p[x] = y;
	if(ranks[x] == ranks[y]) {
	  ++ranks[y];
	}
      }
    }
  }
};

static vector<vector<int>> adj;
static int tim;
static vector<int> ts;
static vector<int> path;

static void dfs(int u) {
  ts[u] = tim++;
  path.push_back(u);
  for(int v : adj[u]) {
    if(ts[v] == -1) {
      dfs(v);
      path.push_back(u);
    }
  }
}

static void find_tree(int n, int m, signed A[], signed B[]) {
  adj.assign(n, vector<int>());
  path.clear();
  tim = 0;
  UnionFind uf(n);
  vector<pair<int, int>> edges(m);
  for(int i = 0; i < m; ++i) {
    edges[i] = {A[i], B[i]};
  }
  for(pair<int, int> p : edges) {
    int u = p.first, v = p.second;
    if(!uf.is_same_set(u, v)) {
      uf.unite(u, v);
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
  }

  ts.assign(n, -1);
  dfs(0);
}

long long Ioi(signed n, signed m, signed A[], signed B[], signed p, signed v, signed T) {
  find_tree(n, m, A, B);
  int seq[60];
  seq[ts[p]%60] = v;
  int i;
  for(i = 0; i < path.size()-1; ++i) {
    if(path[i] == p) {
      break;
    }
  }
  if(path[i] != p) while(true);
  if(path.front() != path.back()) while(true);
  for(int k = 0; k < 120; ++k) {
    int prev = i;
    i = (i+1)%path.size();
    if(i == path.size()-1) {
      i = 0;
    }
    if(find(adj[path[prev]].begin(), adj[path[prev]].end(), path[i]) == adj[path[prev]].end()) while(true);
    int res = Move(path[i]);
    seq[ts[path[i]]%60] = res;
  }
  int X = 0;
  for(int j = 0; j < 60; ++j)
    X |= seq[j] << j;
  return X;
}

Compilation message

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:83:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i = 0; i < path.size()-1; ++i) {
              ~~^~~~~~~~~~~~~~~
Ioi.cpp:93:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i == path.size()-1) {
        ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 752 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5032 KB Output is correct
2 Correct 34 ms 5400 KB Output is correct
3 Correct 30 ms 5400 KB Output is correct
4 Correct 20 ms 5400 KB Output is correct
5 Incorrect 20 ms 5400 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5400 KB Output is correct
2 Correct 4 ms 5400 KB Output is correct
3 Correct 4 ms 5400 KB Output is correct
4 Correct 7 ms 5400 KB Output is correct
5 Correct 7 ms 5400 KB Output is correct
6 Correct 7 ms 5400 KB Output is correct
7 Correct 8 ms 5400 KB Output is correct
8 Correct 8 ms 5400 KB Output is correct
9 Correct 19 ms 5608 KB Output is correct
10 Correct 19 ms 5816 KB Output is correct
11 Correct 20 ms 5816 KB Output is correct
12 Correct 4 ms 5816 KB Output is correct
13 Correct 5 ms 5816 KB Output is correct
14 Correct 5 ms 5816 KB Output is correct
15 Correct 4 ms 5816 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5816 KB Output is correct
2 Correct 34 ms 5816 KB Output is correct
3 Correct 31 ms 5816 KB Output is correct
4 Correct 20 ms 5816 KB Output is correct
5 Incorrect 20 ms 5816 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5816 KB Output is correct
2 Correct 33 ms 5816 KB Output is correct
3 Correct 33 ms 6032 KB Output is correct
4 Correct 22 ms 6248 KB Output is correct
5 Correct 25 ms 6356 KB Output is correct
6 Correct 30 ms 6464 KB Output is correct
7 Correct 22 ms 6464 KB Output is correct
8 Correct 20 ms 6528 KB Output is correct
9 Correct 27 ms 6816 KB Output is correct
10 Correct 19 ms 7040 KB Output is correct
11 Correct 27 ms 7040 KB Output is correct
12 Correct 20 ms 7088 KB Output is correct
13 Correct 23 ms 7176 KB Output is correct
14 Correct 31 ms 7364 KB Output is correct
15 Correct 20 ms 7616 KB Output is correct
16 Correct 20 ms 7940 KB Output is correct
17 Correct 20 ms 8160 KB Output is correct
18 Correct 22 ms 8228 KB Output is correct
19 Correct 22 ms 8400 KB Output is correct
20 Incorrect 17 ms 9040 KB Wrong Answer [7]
21 Halted 0 ms 0 KB -