Submission #986731

#	Time	Username	Problem	Language	Result	Execution time	Memory
986731		AlperenT_	Team Contest (JOI22_team)	C++17	100 / 100	268 ms	73604 KiB

team

#include <bits/stdc++.h>
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <ll,ll>
#define PII pair<pii , pii>
#define ld long double
#define ll long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
const int maxn = 6e5 + 10  , N = 1e5 +1 , lg = 20 , maxq = 202   , inf = 1e9  , maxk = 2022  , mod =998244353;
int a[3][maxn] , id[3] , mark[maxn]; 
vector <int> vec[3][maxn] ;
set <int> s[3] ;

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);   
    int n ;cin >> n ;
    vector <int> cm[4] ;
    rep(i ,1 ,n){
        rep(j ,0 , 2){
            cin >> a[j][i] ;
            cm[j].pb(a[j][i]);
        }
    }
    rep(i , 0 ,2){
        sort(all(cm[i])) ;
    }
    rep(i , 0 , 2)id[i] =sz(cm[i])-1 ;
    rep(i , 1, n){
        rep(j , 0 , 2){
            a[j][i] = lower_bound(all(cm[j]) , a[j][i])-cm[j].begin();
            vec[j][a[j][i]].pb(i) ;
        }
    }
    while(1){
        bool ok =0 ;
        rep(i , 0 , 2)if(sz(s[i]) ==0 )ok=1;
        if(ok == 1){
            ok =0 ; 
            rep(i , 0,2){
                if(sz(s[i])!=0)continue ;
                if(id[i] == -1){
                    ok = 1 ;
                    break ;
                }
                for(int x : vec[i][id[i]]){
                    if(mark[x] == 1)continue;
                    s[i].insert(x);
                }
                id[i]--;
            }
            if(ok == 1)break ;
            continue ;
        }
        while(1){
            ok =0 ;
            rep(i , 0 ,2){
                if(sz(s[i]) == 0)ok = 1; 
            }
            if(ok == 1)break ;
            int b[3] ;
            rep(i , 0,2){
                b[i] = (*s[i].begin()) ;
            }
            int k = -1 ;
            rep(i , 0 ,2){
                rep(j , 0, 2){
                    if(i == j)continue ;
                    if(s[j].find(b[i])!=s[j].end()){
                        k = i ;
                    }
                }
            }
            if(k == -1){
                int ans =0 ;
                rep(i , 0 ,2){
                    ans += cm[i][id[i]+1] ;
                }
                cout << ans << "\n";
                exit(0) ;
            }
            mark[b[k]] = 1; 
            rep(i , 0, 2){
                s[i].erase(b[k]);
            }
        }
    }
    cout << -1 << "\n" ;
}
/*

*/

• 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