oj.uz

Submission #1091730

# Submission time Handle Problem Language Result Execution time Memory
1091730 2024-09-22T01:08:57 Z JeffLegendPower Sirni (COCI17_sirni) C++17
140 / 140
 2317 ms 477440 KB 
// https://oj.uz/problem/view/COCI17_sirni

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

using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define plli pair<ll, int>
#define pll pair<ll, ll>
#define pii pair<int, int>
// Usage: FOR(i, 0, N) {...}
#define FOR(i, start, end) for(int i = start; i < end; i++)

void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

struct comp {
    bool operator() (plli a, plli b) {
        return a < b;
    }
};

typedef tree<plli, null_type, comp, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;


// Segtree start
const int Nmax = 1e5;  // limit for array size
int N;  // array size
int t[2 * Nmax];

int oper(int a, int b) {
    return a + b;
}

void build() {  // build the tree
  for (int i = N - 1; i > 0; --i) t[i] = oper(t[i<<1], t[i<<1|1]);
}

void modify(int p, int value) {  // set value at position p
  for (t[p += N] = value; p > 1; p >>= 1) t[p>>1] = oper(t[p], t[p^1]);
}

int query(int l, int r) {  // on interval [l, r)
  int res = 0;
  for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
    if (l&1) res = oper(res, t[l++]);
    if (r&1) res = oper(res, t[--r]);
  }
  return res;
}
// Segtree end

class DSU {
  private:
	vector<int> parents;
	vector<int> sizes;

  public:
	DSU(int size) : parents(size), sizes(size, 1) {
		for (int i = 0; i < size; i++) { parents[i] = i; }
	}

	/** @return the "representative" node in x's component */
	int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }

	/** @return whether the merge changed connectivity */
	bool unite(int x, int y) {
		int x_root = find(x);
		int y_root = find(y);
		if (x_root == y_root) { return false; }

		if (sizes[x_root] < sizes[y_root]) { swap(x_root, y_root); }
		sizes[x_root] += sizes[y_root];
		parents[y_root] = x_root;
		return true;
	}

	/** @return whether x and y are in the same connected component */
	bool connected(int x, int y) { return find(x) == find(y); }
};

int main() {
    // Comment out for interactive problems
    ios::sync_with_stdio(false);
	cin.tie(nullptr);

    int N;
    cin >> N;

    int M = 1e7 + 1;

    set<int> Pset;
    for (int i = 0; i < N; i++) {
        int P;
        cin >> P;
        Pset.insert(P);
    }

    int n = Pset.size();

    int P[n];
    int idx = 0;
    for (auto itr = Pset.begin(); itr != Pset.end(); itr++) P[idx++] = *itr;

    vector<vector<pii>> edges;
    edges.reserve(M);

    for (int i = 0; i < n; i++) {
        int j = i + 1;
        for (int p = P[i]; p < M; p += P[i]) {
            while (j < n && P[j] < p) j++;

            if (j < n) edges[P[j] % P[i]].push_back({i, j});
        }
    }

    DSU dsu(N);
    ll candies = 0;
    for (int m = 0; m < M; m++) {
        for (pii edge : edges[m]) {
            if (dsu.connected(edge.first, edge.second)) continue;
            dsu.unite(edge.first, edge.second);
            candies += m;
        }
    }

    cout << candies;
}

Compilation message

sirni.cpp: In function 'void setIO(std::string)':
sirni.cpp:18:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:19:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2136 KB Output is correct
2 Correct 60 ms 31824 KB Output is correct
3 Correct 14 ms 2648 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 856 KB Output is correct
2 Correct 706 ms 397140 KB Output is correct
3 Correct 13 ms 2904 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2056 KB Output is correct
2 Correct 12 ms 1700 KB Output is correct
3 Correct 18 ms 2396 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1652 ms 16628 KB Output is correct
2 Correct 1510 ms 44792 KB Output is correct
3 Correct 1112 ms 26372 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3668 KB Output is correct
2 Correct 115 ms 25680 KB Output is correct
3 Correct 1234 ms 15892 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1606 ms 28256 KB Output is correct
2 Correct 1835 ms 61320 KB Output is correct
3 Correct 1543 ms 24732 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 6540 KB Output is correct
2 Correct 1121 ms 61588 KB Output is correct
3 Correct 1266 ms 25920 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1135 ms 20308 KB Output is correct
2 Correct 1794 ms 364372 KB Output is correct
3 Correct 1188 ms 23200 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1188 ms 24256 KB Output is correct
2 Correct 2317 ms 477440 KB Output is correct
3 Correct 1255 ms 79028 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 4352 KB Output is correct
2 Correct 1855 ms 365528 KB Output is correct
3 Correct 1449 ms 28244 KB Output is correct