oj.uz

Submission #736158

# Submission time Handle Problem Language Result Execution time Memory
736158 2023-05-05T09:10:16 Z marvinthang Sjekira (COCI20_sjekira) C++17
110 / 110
 37 ms 4312 KB 
/******************************
*    author : @marvinthang    *
*    date : 27 / 12 / 2021    *
******************************/

#include <bits/stdc++.h>

using namespace std;

#define  superspeed  ios_base::sync_with_stdio(false); cin.tie(nullptr); //cout.tie(nullptr);
#define  file(name)  if (fopen (name".inp", "r") ) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }

template <class U, class V> ostream & operator << (ostream& out, const pair<U, V> &p) { return out << '(' << p.first << ", " << p.second << ')'; }
template <class T> ostream & operator << (ostream &out, const vector<T> &vt) { out << '['; for (size_t i = 0; i + 1 < vt.size(); i++) out << vt[i] << ", "; if (!vt.empty()) out << vt.back(); return out << ']'; }

const 		int MOD = 1e9 + 7;
const     double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const      int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const  long long oo = 1e18;
const       int MAX = 1e5 + 5;

int N, T[MAX];

struct Edge {
	int u, v;

	bool operator < (const Edge &other) const {
		return max(T[u], T[v]) < max(T[other.u], T[other.v]);
	}
} edges[MAX];

struct DisjointSet {
    
    static const int MAXN = 1e5 + 5;

    int par[MAXN] = {}, maxVal[MAXN];

    DisjointSet(int n = 0) {
        for (int i = 1; i <= n; ++i) par[i] = -1, maxVal[i] = T[i];
    }

    int findSet(int u) {
        return par[u] < 0 ? u : par[u] = findSet(par[u]);
    }

    int unionSet(int u, int v) {
        if ((u = findSet(u)) == (v = findSet(v))) return 0;
        if (par[u] > par[v]) swap(u, v);
        par[u] += par[v];
        par[v] = u;
        int res = maxVal[u] + maxVal[v];
        maxVal[u] = max(maxVal[u], maxVal[v]);
        return res;
    }

};

int main(void) {
    superspeed;
    file("chvpt_sjekira");
    cin >> N;
    for (int i = 1; i <= N; ++i) cin >> T[i];
    DisjointSet dsu(N);
    for (int i = 1; i < N; ++i) cin >> edges[i].u >> edges[i].v;
    sort(edges + 1, edges + N);
	long long res = 0;
	for (int i = 1; i < N; ++i) {
		res += dsu.unionSet(edges[i].u, edges[i].v);
	}
	cout << res << '\n';
    return 0;
}

Compilation message

sjekira.cpp: In function 'int main()':
sjekira.cpp:11:62: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define  file(name)  if (fopen (name".inp", "r") ) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                      ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sjekira.cpp:60:5: note: in expansion of macro 'file'
   60 |     file("chvpt_sjekira");
      |     ^~~~
sjekira.cpp:11:96: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define  file(name)  if (fopen (name".inp", "r") ) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                        ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sjekira.cpp:60:5: note: in expansion of macro 'file'
   60 |     file("chvpt_sjekira");
      |     ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1112 KB Output is correct
5 Correct 1 ms 980 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3744 KB Output is correct
2 Correct 24 ms 3020 KB Output is correct
3 Correct 24 ms 3020 KB Output is correct
4 Correct 26 ms 3220 KB Output is correct
5 Correct 37 ms 4312 KB Output is correct
6 Correct 37 ms 4300 KB Output is correct
7 Correct 35 ms 3988 KB Output is correct
8 Correct 27 ms 3584 KB Output is correct
9 Correct 20 ms 2772 KB Output is correct
10 Correct 36 ms 4260 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1112 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 1 ms 1120 KB Output is correct
10 Correct 1 ms 1108 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1112 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 32 ms 3744 KB Output is correct
7 Correct 24 ms 3020 KB Output is correct
8 Correct 24 ms 3020 KB Output is correct
9 Correct 26 ms 3220 KB Output is correct
10 Correct 37 ms 4312 KB Output is correct
11 Correct 37 ms 4300 KB Output is correct
12 Correct 35 ms 3988 KB Output is correct
13 Correct 27 ms 3584 KB Output is correct
14 Correct 20 ms 2772 KB Output is correct
15 Correct 36 ms 4260 KB Output is correct
16 Correct 1 ms 1108 KB Output is correct
17 Correct 1 ms 1108 KB Output is correct
18 Correct 2 ms 1116 KB Output is correct
19 Correct 1 ms 1120 KB Output is correct
20 Correct 1 ms 1108 KB Output is correct
21 Correct 9 ms 1748 KB Output is correct
22 Correct 7 ms 1632 KB Output is correct
23 Correct 35 ms 4132 KB Output is correct
24 Correct 26 ms 3272 KB Output is correct
25 Correct 28 ms 3172 KB Output is correct
26 Correct 20 ms 2532 KB Output is correct
27 Correct 22 ms 2788 KB Output is correct
28 Correct 25 ms 3032 KB Output is correct
29 Correct 16 ms 2388 KB Output is correct
30 Correct 37 ms 4268 KB Output is correct