Submission #716376

#	Time	Username	Problem	Language	Result	Execution time	Memory
716376		Urvuk3	T-Covering (eJOI19_covering)	C++17	100 / 100	623 ms	41864 KiB

covering

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int INF=1e9,MOD=1e9+7;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back

void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}

template<typename T,typename V>
void PRINT(pair<T,V>& x){
    cerr<<"{";
    PRINT(x.fi);
    cerr<<",";
    PRINT(x.se);
    cerr<<"}";
}
template<typename T>
void PRINT(T &x){
    int id=0;
    cerr<<"{";
    for(auto _i:x){
        cerr<<(id++ ? "," : "");
        PRINT(_i);
    }
    cerr<<"}";
}
void _PRINT(){
    cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
    PRINT(h);
    if(sizeof...(t)) cerr<<", ";
    _PRINT(t...);
}

#define Debug(x...) cerr<<"["<<#x<<"]=["; _PRINT(x)

int N,M,K;
vector<vector<ll>> a;
set<pii> special,special1;
vector<pii> comp;
set<pair<ll,pii>> adja;
vector<int> di={1,0,-1,0},dj={0,1,0,-1};
vector<int> dis={1,2,0,0,-1,-2,0,0,1,-1,-1,1};
vector<int> djs={0,0,1,2,0,0,-1,-2,1,1,-1,-1};

bool Valid(int i,int j){
    return (1<=i && i<=N) && (1<=j && j<=M);
}

void Dfs(int i,int j){
    comp.pb({i,j});
    special.erase(special.find({i,j}));
    for(int d=0;d<12;d++){
        int in=i+dis[d],jn=j+djs[d];
        if(special.count({in,jn})){
            Dfs(in,jn);
        }
    }
}

void Solve(){
    cin>>N>>M;
    a.resize(N+1);
    for(int i=1;i<=N;i++){
        a[i].resize(M+1);
        for(int j=1;j<=M;j++){
            cin>>a[i][j];
        }
    }
    cin>>K;
    for(int i=1;i<=K;i++){
        int is,js; cin>>is>>js; is++,js++;
        special.insert({is,js});
        special1.insert({is,js});
    }
    //Debug(special);
    ll res=0;
    while(!special.empty()){
        pii p=*special.begin();
        Dfs(p.fi,p.se);
        //Debug(comp);
        for(pii p:comp){
            int i=p.fi,j=p.se;
            for(int d=0;d<4;d++){
                int in=i+di[d];
                int jn=j+dj[d];
                if(Valid(in,jn) && !special1.count({in,jn})){
                    adja.insert({a[in][jn],{in,jn}});
                }
            }
        }
        //Debug(adja);
        int k=sz(comp);
        if(sz(adja)<3*k){
            cout<<"No"<<endl;
            return;
        }
        else if(sz(adja)==3*k){
            for(auto p:adja){
                res+=p.fi;
            }
            for(auto p:comp){
                res+=a[p.fi][p.se];
            }
        }
        else{
            ll mn=INF;
            for(auto p:adja){
                res+=p.fi;
                mn=min(mn,p.fi);
            }
            for(auto p:comp){
                res+=a[p.fi][p.se];
            }
            res-=mn;
        }
        comp.clear();
        adja.clear();
    }
    cout<<res<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t; t=1;
    //cin>>t;
    while(t--){
        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