oj.uz

Submission #96112

# Submission time Handle Problem Language Result Execution time Memory
96112 2019-02-06T02:56:09 Z _DeSeiSH_ Synchronization (JOI13_synchronization) C++17
10 / 100
 8000 ms 263168 KB 
//In the name of God
#pragma comment(linker, "/stack:20000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/detail/standard_policies.hpp>

#define debug(...) fprintf(stderr, __VA_ARGS__)

using namespace std;
using namespace __gnu_pbds;

const char nxtl = '\n';
const int inf = (int)2e9 + 228;
const double eps = (double)1e-7;
const int mod = (int)1e9 + 7;

template<typename T>
inline bool updmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}

template<typename T>
inline bool updmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T1, typename T2>
using ordered_map = tree<T1, T2, less<T1>, rb_tree_tag, tree_order_statistics_node_update>;

int pr[100005], depth[100005];
unordered_map<int, bool>have[100005];

void dfs(int v, int p) {
  depth[v] = depth[p] + 1;
  for(auto &to : have[v]) {
    if(to.first == p) {
      continue;
    }
    dfs(to.first, v);
  }
}

int GetPr(int x) {
  return pr[x] == x ? x : GetPr(pr[x]);
}

vector<int>ans[100005];

inline void Split(int x, int y) {
  if(depth[x] < depth[y]) {
    swap(x, y);
  }
  pr[x] = x;
  y = GetPr(y);
  ans[x] = ans[y];
}

inline void Merge(int x, int y) {
  if(depth[x] < depth[y]) {
    swap(x, y);
  }
  pr[x] = y;
  y = GetPr(y);
  for(auto &to : ans[x]) {
    ans[y].push_back(to);
  }
  sort(ans[y].begin(), ans[y].end());
  ans[y].resize(unique(ans[y].begin(), ans[y].end()) - ans[y].begin());
}

inline int get(int v) {
  return (int)ans[v].size();
}

int x[100005], y[100005], d[200005], c[100005];

signed main() {
#ifdef LOCAL
  freopen(".in", "r", stdin);
  freopen("slow.out", "w", stdout);
#endif
//  ios_base::sync_with_stdio(0);
//  cin.tie(0);
  unsigned int FOR;
  asm("rdtsc" : "=A"(FOR));
  srand(FOR);
  int n, m, q;
  scanf("%d %d %d\n", &n, &m, &q);
  for(int i = 1; i < n; ++i) {
    scanf("%d %d\n", x + i, y + i);
    have[x[i]][y[i]] = have[y[i]][x[i]] = 0;
  }
  for(int i = 1; i <= n; ++i) {
    pr[i] = i;
    ans[i].push_back(i);
  }
  dfs(1, -1);
  for(int i = 1; i <= m; ++i) {
    scanf("%d\n", d + i);
    if(have[x[d[i]]][y[d[i]]]) {
      Split(x[d[i]], y[d[i]]);
    } else {
      Merge(x[d[i]], y[d[i]]);
    }
    have[x[d[i]]][y[d[i]]] = have[y[d[i]]][x[d[i]]] ^= 1;
  }
  for(int i = 1; i <= q; ++i) {
    scanf("%d\n", c + i);
    c[i] = GetPr(c[i]);
    printf("%d\n", get(c[i]));
  }
  return 0;
}

Compilation message

synchronization.cpp:2:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:20000000")
 
synchronization.cpp: In function 'int main()':
synchronization.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d\n", &n, &m, &q);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d\n", x + i, y + i);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n", d + i);
     ~~~~~^~~~~~~~~~~~~~~
synchronization.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n", c + i);
     ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct
5 Correct 9 ms 8184 KB Output is correct
6 Correct 12 ms 8440 KB Output is correct
7 Correct 46 ms 11768 KB Output is correct
8 Correct 43 ms 11384 KB Output is correct
9 Correct 70 ms 12820 KB Output is correct
10 Correct 909 ms 65704 KB Output is correct
11 Correct 765 ms 55912 KB Output is correct
12 Correct 316 ms 29996 KB Output is correct
13 Execution timed out 8077 ms 137368 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8074 ms 25856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 12 ms 8184 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct
5 Correct 11 ms 8184 KB Output is correct
6 Correct 10 ms 8440 KB Output is correct
7 Correct 25 ms 10488 KB Output is correct
8 Correct 361 ms 31108 KB Output is correct
9 Correct 375 ms 31120 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 31064 KB Output is correct
2 Runtime error 1894 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 8 ms 8184 KB Output is correct
3 Correct 8 ms 8184 KB Output is correct
4 Correct 8 ms 8184 KB Output is correct
5 Correct 10 ms 8440 KB Output is correct
6 Correct 50 ms 12408 KB Output is correct
7 Correct 983 ms 65160 KB Output is correct
8 Correct 354 ms 31224 KB Output is correct
9 Execution timed out 8074 ms 127404 KB Time limit exceeded
10 Halted 0 ms 0 KB -