Submission #753414

#	Time	Username	Problem	Language	Result	Execution time	Memory
753414		MateiKing80	T-Covering (eJOI19_covering)	C++14	100 / 100	358 ms	45172 KiB

covering

#include <bits/stdc++.h>

using namespace std;

int m,n;

int fct(int x, int y)
{
    x--;
    y--;
    return m*x+y;
}

int v[1000005];
int f[1000005];
bool viz[1000005];
pair<int,int>red[1000005];
bool oc[1000005];
vector<int>graf[1000005];



struct sus
{
    int nrmuch=0, nrnod=0, minn=2100000000;
};


sus dfs(int nod)
{
    sus ans;
    if(viz[nod])
        return ans;
    viz[nod]=true;
    ans.nrnod=1;
    ans.nrmuch=graf[nod].size();
    int a=red[nod].first;
    int b=red[nod].second;
    if(a>1)
        ans.minn=min(ans.minn,v[fct(a-1,b)]),oc[fct(a-1,b)]=true;
    if(b>1)
        ans.minn=min(ans.minn,v[fct(a,b-1)]),oc[fct(a,b-1)]=true;
    if(b<m)
        ans.minn=min(ans.minn,v[fct(a,b+1)]),oc[fct(a,b+1)]=true;
    if(a<n)
        ans.minn=min(ans.minn,v[fct(a+1,b)]),oc[fct(a+1,b)]=true;
    for(int i=0;i<graf[nod].size();i++)
    {
        sus p=dfs(graf[nod][i]);
        ans.nrnod+=p.nrnod;
        ans.nrmuch+=p.nrmuch;
        ans.minn=min(ans.minn,p.minn);
    }
    return ans;
}





int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>v[fct(i,j)];
    int k;
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>red[i].first>>red[i].second;
        red[i].first++;
        red[i].second++;
        oc[fct(red[i].first,red[i].second)]=true;
        f[fct(red[i].first,red[i].second)]=i;
    }
    for(int i=1;i<=k;i++)
    {
        int a=red[i].first;
        int b=red[i].second;
        if(a==1)
            graf[i].push_back(i),graf[i].push_back(i);
        if(a==n)
            graf[i].push_back(i),graf[i].push_back(i);
        if(b==1)
            graf[i].push_back(i),graf[i].push_back(i);
        if(b==m)
            graf[i].push_back(i),graf[i].push_back(i);
        if(a>1 && b<m && f[fct(a-1,b+1)])
            graf[i].push_back(f[fct(a-1,b+1)]),graf[f[fct(a-1,b+1)]].push_back(i),graf[i].push_back(f[fct(a-1,b+1)]),graf[f[fct(a-1,b+1)]].push_back(i);
        if(b<m && f[fct(a,b+1)])
            graf[i].push_back(f[fct(a,b+1)]),graf[f[fct(a,b+1)]].push_back(i),graf[i].push_back(f[fct(a,b+1)]),graf[f[fct(a,b+1)]].push_back(i);
        if(b<m-1 && f[fct(a,b+2)])
            graf[i].push_back(f[fct(a,b+2)]),graf[f[fct(a,b+2)]].push_back(i);
        if(b<m && a<n && f[fct(a+1,b+1)])
            graf[i].push_back(f[fct(a+1,b+1)]),graf[f[fct(a+1,b+1)]].push_back(i),graf[i].push_back(f[fct(a+1,b+1)]),graf[f[fct(a+1,b+1)]].push_back(i);
        if(a<n && f[fct(a+1,b)])
            graf[i].push_back(f[fct(a+1,b)]),graf[f[fct(a+1,b)]].push_back(i),graf[i].push_back(f[fct(a+1,b)]),graf[f[fct(a+1,b)]].push_back(i);
        if(a<n-1 && f[fct(a+2,b)])
            graf[i].push_back(f[fct(a+2,b)]),graf[f[fct(a+2,b)]].push_back(i);

    }
    int ans=0;
    for(int i=1;i<=k;i++)
    {
        if(!viz[i])
        {
            sus x=dfs(i);
            x.nrmuch/=2;
            if(x.nrmuch<x.nrnod)
                ans+=x.minn;
            if(x.nrmuch>x.nrnod)
            {
                cout<<"No";
                return 0;
            }
        }
    }
    int ras=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(oc[fct(i,j)])
                ras+=v[fct(i,j)];
    cout<<ras-ans;
}

Compilation message (stderr)

covering.cpp: In function 'sus dfs(int)':
covering.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<graf[nod].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~

• 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