제출 #748592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748592		GrindMachine	Team Contest (JOI22_team)	C++17	100 / 100	713 ms	79348 KiB

team

// Om Namah Shivaya

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

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi
https://github.com/koosaga/olympiad/blob/master/JOI/camp22_team.cpp

let's look at the initial array
when will some guy definitely not be in the best triplet?
=> if he dominates in >= 2 areas

so we can remove all guys who cant be there

repeat the process on the resulting array
repeat until we can no longer delete anyone

what does it mean if we can make no more deletions?
there is exactly 1 guy dominating each area

so we can pick the guy dominating each area and that would be our triplet

if < 3 guys are remaining, then not possible

naive simulation of this process = O(n^2)

we can efficiently simulate the process using multiset and map

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    ll n; cin >> n;
    vector<array<ll,3>> a(n);
    rep(i,n) rep(j,3) cin >> a[i][j];

    multiset<ll> ms[3];
    rep(i,n){
        rep(j,3){
            ms[j].insert(a[i][j]);
        }
    }

    array<ll,3> mxs;
    rep(j,3) mxs[j] = *ms[j].rbegin();

    vector<ll> cnt(n);
    queue<ll> q;

    rep(i,n){
        rep(j,3){
            if(a[i][j] == mxs[j]){
                cnt[i]++;
            }
        }

        if(cnt[i] >= 2){
            q.push(i);
        }
    }

    map<ll,vector<ll>> mp[3];
    rep(i,n){
        rep(j,3){
            mp[j][a[i][j]].pb(i);
        }
    }

    vector<bool> rem(n);
    ll rem_cnt = 0;

    while(!q.empty()){
        ll i = q.front();
        q.pop();

        if(rem[i]) conts;
        rem[i] = 1;
        rem_cnt++;

        if(rem_cnt == n){
            cout << -1 << endl;
            return;
        }

        rep(j,3){
            ms[j].erase(ms[j].find(a[i][j]));
        }

        array<ll,3> mxs_new;
        rep(j,3){
            mxs_new[j] = *ms[j].rbegin();
        }

        rep(j,3){
            if(mxs_new[j] != mxs[j]){
                trav(i,mp[j][mxs_new[j]]){
                    if(rem[i]) conts;
                    cnt[i]++;
                    if(cnt[i] >= 2){
                        q.push(i);
                    }
                }
            }
        }

        mxs = mxs_new;
    }

    ll ans = 0;
    rep(j,3) ans += mxs[j];

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 27 / 27