oj.uz

Submission #590886

# Submission time Handle Problem Language Result Execution time Memory
590886 2022-07-06T12:57:08 Z marvinthang Synchronization (JOI13_synchronization) C++17
100 / 100
 304 ms 25852 KB 
/*************************************
*    author: marvinthang             *
*    created: 06.07.2022 19:35:12    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                 div  ___div
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define             FULL(i)  (MASK(i) - 1)
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }

template <class T>             scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class T>            print_op(vector <T>)  { out << '{'; for (size_t i = 0; i + 1 < u.size(); ++i) out << u[i] << ", "; if (!u.empty()) out << u.back(); return out << '}'; }
template <class U, class V>   scan_op(pair <U, V>)  { return in >> u.fi >> u.se; }
template <class U, class V>  print_op(pair <U, V>)  { return out << '(' << u.fi << ", " << u.se << ')'; }

const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {1, 0, -1, 0, 1, 1, -1, -1, 1};
const int MAX = 1e5 + 5;
const int LOG = 20;

// index from 0

template <class T>
    struct Fenwick {

        T *bit;
        int n;

        Fenwick(int _n = 0) {
            n = _n;
            bit = new T[n + 1];
            reset();
        }

        void reset(void) {
            fill(bit, bit + 1 + n, T(0));
        }

        void update(int i, T val) {
            assert(0 <= i);
            ++i;
            for (; i <= n; i += i & -i) bit[i] += val;
        }

        void update(int l, int r, T val) {
            if (l > r) return;
            update(l, val);
            update(r + 1, -val);
        }

        T get(int i) {
            if (i < 0) return T(0);
            ++i;
            i = min(i, n);
            T res = 0;
            for (; i > 0; i -= i & -i)
                res += bit[i];
            return res;
        }

        T get(int l, int r) {
            if (l > r) return T(0);
            return get(r) - get(l - 1);
        }

        int upper_bound(T val) {
            int res = 0;
            T sum = 0;
            for (int i = __lg(n); i >= 0; --i) {
                if ((res | 1 << i) <= n && sum + bit[res | 1 << i] <= val) {
                    res |= 1 << i;
                    sum += bit[res];
                }
            }
            return res;
        }

        int lower_bound(T val) {
            int res = 0;
            T sum = 0;
            for (int i = __lg(n); i >= 0; --i) {
                if ((res | 1 << i) <= n && sum + bit[res | 1 << i] < val) {
                    res |= 1 << i;
                    sum += bit[res];
                }
            }
            return res;
        }

    };


int numNode, numQuery, numChange, res[MAX], anc[MAX][LOG], left[MAX], right[MAX], same[MAX];
bool exist[MAX];
vector <int> adj[MAX];
vector <pair <int, int>> edges;
Fenwick <int> bit;

void dfs(int u) {
	static int timeDfs = 0;
	left[u] = ++timeDfs;
	for (int i = 1; i < LOG; ++i) anc[u][i] = anc[anc[u][i - 1]][i - 1];
	for (int &v: adj[u]) if (v != anc[u][0]) {
		anc[v][0] = u;
		dfs(v);
	}
	right[u] = timeDfs;
}

int find(int u) {
	for (int i = LOG; i--; ) if (bit.get(left[u]) - bit.get(left[anc[u][i]]) == MASK(i)) u = anc[u][i];
	return u;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("I");
	cin >> numNode >> numChange >> numQuery;
	for (int i = 1; i < numNode; ++i) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		edges.push_back(make_pair(u, v));
	}
	bit = Fenwick<int> (numNode + 1);
	dfs(1);
	fill(res + 1, res + 1 + numNode, 1);
	while (numChange--) {
		int i; cin >> i; --i;
		int u = edges[i].fi, v = edges[i].se;
		if (anc[u][0] == v) swap(u, v);
		u = find(u);
		if (!exist[i]) {
			same[i] = res[u] = res[u] + res[v] - same[i];
			bit.update(left[v], right[v], 1);
		} else {
			same[i] = res[v] = res[u];
			bit.update(left[v], right[v], -1);
		}
		exist[i] ^= 1;
	}
	while (numQuery--) {
		int u; cin >> u; cout << res[find(u)] << '\n';
	}
	cerr << "Time elapsed: " << TIME << " s.\n";
	return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:22:69: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:130:2: note: in expansion of macro 'file'
  130 |  file("I");
      |  ^~~~
synchronization.cpp:22:103: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                               ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:130:2: note: in expansion of macro 'file'
  130 |  file("I");
      |  ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 15 ms 4260 KB Output is correct
8 Correct 14 ms 4328 KB Output is correct
9 Correct 17 ms 4224 KB Output is correct
10 Correct 244 ms 18880 KB Output is correct
11 Correct 189 ms 18960 KB Output is correct
12 Correct 211 ms 25008 KB Output is correct
13 Correct 107 ms 18764 KB Output is correct
14 Correct 156 ms 18240 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 21816 KB Output is correct
2 Correct 106 ms 21568 KB Output is correct
3 Correct 106 ms 24436 KB Output is correct
4 Correct 105 ms 24364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2676 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 4 ms 2820 KB Output is correct
7 Correct 20 ms 4968 KB Output is correct
8 Correct 289 ms 25852 KB Output is correct
9 Correct 286 ms 25776 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 25776 KB Output is correct
2 Correct 163 ms 25404 KB Output is correct
3 Correct 161 ms 25536 KB Output is correct
4 Correct 172 ms 25636 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 22 ms 4356 KB Output is correct
7 Correct 304 ms 19688 KB Output is correct
8 Correct 260 ms 25780 KB Output is correct
9 Correct 171 ms 19832 KB Output is correct
10 Correct 183 ms 19564 KB Output is correct
11 Correct 154 ms 22892 KB Output is correct
12 Correct 157 ms 22968 KB Output is correct
13 Correct 159 ms 25536 KB Output is correct