Submission #1284835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284835		warrenn	T-Covering (eJOI19_covering)	C++20	0 / 100	151 ms	12452 KiB

covering

#include<bits/stdc++.h>
using namespace std; 
#define int long long 
#pragma GCC optimize("O3,unroll-loops")

const int maxn=1e6;

int a[maxn+2];
bool spec[maxn+2],vis[maxn+2];
int n,m;

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

bool ins(int x,int y){
    return (x>=0 && y>=0 && x<n && y<m);
}

vector<int>adj[maxn+2];
vector<int>node;
int cnt=0;

void dfs(int cur){
    vis[cur]=true;

    if(!spec[cur]){
        node.push_back(a[cur]);
    }
    else{
        cnt++;
    }

    for(auto x :adj[cur]){
        if(vis[x])continue;
        dfs(x);
    }
}


signed main(){
    cin>>n>>m;
    for(int q=0;q<n;q++){
        for(int w=0;w<m;w++){
            int id=(q-1)*m+w;
            assert(id<=maxn);
            cin>>a[id];
        }
    }

    int qu;
    cin>>qu;

    int ans=0;

    while(qu--){
        int x,y;
        cin>>x>>y;
        int id=(x-1)*m+y;
        ans+=a[id];
        spec[id]=true;

        for(int q=0;q<4;q++){
            int nx=x+dx[q];
            int ny=y+dy[q];
            if(ins(nx,ny)){
                int baru=(nx-1)*m+ny;
                assert(baru<=maxn);
                adj[id].push_back(baru);
                adj[baru].push_back(id);
            }
        }
    }


    for(int q=0;q<n*m;q++){
        if(spec[q] && vis[q]==false){
            cnt=0; node.clear();
            dfs(q);
            if(node.size()<3*cnt){
                cout<<"No"<<endl;
                return 0;
            }
            
            sort(node.rbegin(),node.rend());
            for(int q=0;q<3*cnt;q++){
                ans+=node[q];
            }
        }
    }
    cout<<ans<<endl;
}

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