Submission #1137277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137277		Dragos1	T-Covering (eJOI19_covering)	C++20	25 / 100	258 ms	113056 KiB

covering

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
int n,m,k,x,y;
vector<int> mat;
unordered_map<int,bool> vis,este;
vector<vector<int>> graf;
vector<int> cate;
int ans=0,centre;
int di[]={1,0,-1,0};
int dj[]={0,1,0,-1};
bool inmat(int i,int j)
{
    return i>=0 && j>=0 && i<n && j<m;
}
void dfs(int cur)
{
    vis[cur]=1;
    if(!este[cur])
        cate.push_back(mat[cur]);
    else{
        centre++;
    }
    for(auto urm:graf[cur])
    {
        if(!vis[urm])
            dfs(urm);
    }
}
int main()
{
    cin>>n>>m;
    mat.resize(n*m+10);
    graf.resize(n*m+10);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            int aux=i*m+j;
            cin>>mat[aux];
            este[aux]=0;
            vis[aux]=0;
        }
    }
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>x>>y;
        int aux=x*m+y;
        este[aux]=true;
        ans+=mat[aux];
        for(int d=0;d<4;d++)
        {
            int urm1=x+di[d];
            int urm2=y+dj[d];
            if(inmat(urm1,urm2)){
               int auxx=urm1*m+urm2;
               graf[aux].push_back(auxx);
               graf[auxx].push_back(aux);
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            int aux=i*m+j;
            if(!vis[aux] && este[aux])
            {
                centre=0;
                cate.clear();
                dfs(aux);
                if(int(cate.size())<centre*3){
                    cout<<"No";
                    return 0;
                }
                sort(cate.begin() , cate.end());
                for(int care=1;care<=3*centre;care++){
                    ans+=cate[int(cate.size())-care];
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

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