Submission #715167

#	Time	Username	Problem	Language	Result	Execution time	Memory
715167		aykhn	Sirni (COCI17_sirni)	C++14	42 / 140	779 ms	786432 KiB

sirni

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define OPT ios_base::sync_with_stdio(0); \
            cin.tie(0); \
            cout.tie(0)

#define pii pair<int,int>
#define pll pair<ll,ll>
#define endl "\n"
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define inf 0x3F3F3F3F
#define bpc __builtin_popcount
#define print(v) for(int i = 0; i < v.size(); i++) \
                    cout << v[i] << " "; \
                    cout<<endl;

struct DSU {
	vector<int> e;

	void init(int n)
	{
	    e.assign(n, -1);
	}

	int get(int x)
	{
	    if (e[x] < 0)
            return x;
        return get(e[x]);
	}

	bool together(int a, int b)
	{
	    if (get(a) == get(b))
            return true;
        return false;
	}

	int s(int x)
	{
	    return -e[get(x)];
	}

	bool un(int x, int y)
	{
		x = get(x);
        y = get(y);

		if (x == y) return false;

		if (e[x] > e[y]) swap(x, y);

		e[x] += e[y];
		e[y] = x;

		return true;
	}
};

int n;

int main()
{
    cin >> n;
    vector<int> v(n, 0);
    vector<pair<int, pii>> edges;

    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            edges.pb(mpr(min(v[i] % v[j], v[j] % v[i]), mpr(i, j)));
        }
    }

    sort(all(edges));

    DSU dsu;

    dsu.init(n);

    ll ans = 0;

    for (int i = 0; i < edges.size(); i++)
    {
        if (dsu.together(edges[i].se.fi, edges[i].se.se)) continue;

        ans = ans + edges[i].fi;

        dsu.un(edges[i].se.fi, edges[i].se.se);
    }

    cout << ans << endl;
}

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int i = 0; i < edges.size(); i++)
      |                     ~~^~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14