Submission #1096287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096287		YFHHFY	T-Covering (eJOI19_covering)	C++14	100 / 100	199 ms	57040 KiB

covering

#include<bits/stdc++.h>
#define tizoboz ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define pb push_back
// #define int long long
#define itn int
#define ss set <int>
#define prq priority_queue <int>
#define endl '\n'
const ll MOD = 1e9 + 7;
#define md(x) (((x%MOD)+MOD)%MOD)
#define vi vector <int>
#define vl vector<ll>
#define str string 
#define mp make_pair
#define mata int32_t
#define sz size
#define lc id *2
#define rc lc +1
#define SZ(x)           (int)x.size()
#define mid (l+r)/2
#define cn cin
#define ct cout
#define sep " "
#define F first
#define X first
#define S second
#define Y second
using namespace std;
typedef pair <int , int> pii;
const ll maxn = 1e6 + 85 ;
set <pii> s;
const int Lg = 23;
const ll inf = 1e18 ;
itn n , m , k , g[maxn] , noans;
vi adj[maxn] , vv;
int hx[] = {-1, 1, 0, 0};
int hy[] = {0, 0, 1, -1};
bool vis [maxn] , ok[maxn];
bool verif(int i,int j){return (i >= 0 && i < n && j >= 0 && j < m);}
void dfs(int v){
    vis[v] = 1;
    if (!ok[v]){
        vv.pb(g[v]);
    }
    else{
        noans++;
    }
    for (auto u : adj[v]){
        if (vis[u]){
            continue;
        }
        dfs(u);
    }
}
void solve(){
    cn >> n >> m;
    for (int i = 0 ; i < n ; i ++){
        for (int j = 0 ; j < m ; j ++){
            int v = i*m+j;
            cn >> g[v];
            ok[v] = vis[v] = 0;
        }
    }
    cn >> k;
    ll ans = 0;
    for (int i = 0 ; i < k ; i ++){
        int r , c;
        cn >> r >> c;
        int v = r*m + c;
        ok[v] = 1 , ans += g[v];
        for (int j = 0 ; j < 4 ; j ++){
            int xx = r + hx[j] , yy = c + hy[j];
            if (!verif(xx , yy)){
                continue;
            }
            int u = (xx*m)+ yy;
            adj[v].pb(u);
            adj[u].pb(v);
        }
    }
    for (int i = 0 ; i < n ; i ++){
        for (int j = 0; j < m ; j++){
            int v = i*m+j;
            if (!vis[v] && ok[v]){
                noans = 0;
                vv.clear();
                dfs(v);
                if (SZ(vv) < 3*noans){
                    ct << "No" << endl;
                    return ;
                }
                sort (vv.begin() , vv.end());
                for (int k = 1 ; k <= 3*noans ; k++){
                    ans += vv[SZ(vv) - k];
                }
            }
        }
    }
    ct << ans << endl;
}
mata main(){
    tizoboz;
    int tt = 1;
    // cn >> tt;
    while (tt--){
        solve();
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 30 / 30