Submission #887535

#	Time	Username	Problem	Language	Result	Execution time	Memory
887535		maxFedorchuk	T-Covering (eJOI19_covering)	C++14	100 / 100	235 ms	77416 KiB

covering

#include <bits/stdc++.h>
using namespace std;

const long long MX=1e6+10;

vector < long long > mas[MX];

long long vis[MX];
long long sm[MX];
long long a[MX];

long long n,m;

long long corx[4]={0,0,1,-1};
long long cory[4]={1,-1,0,0};

vector < long long > ver;
long long kver;

long long prd(long long x,long long y)
{
    return (x*m+y);
}

void DFS(long long zar)
{
    if(sm[zar])
    {
        kver++;
    }
    else
    {
        ver.push_back(a[zar]);
    }

    vis[zar]=1;

    for(auto u:mas[zar])
    {
        if(!vis[u])
        {
            DFS(u);
        }
    }

    return;
}

bool can_go(long long x,long long y)
{
    return (0<=x && x<n && 0<=y && y<m);
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin>>n>>m;

    long long zn;
    for(long long i=0;i<n;i++)
    {
        for(long long j=0;j<m;j++)
        {
            cin>>zn;
            a[prd(i,j)]=zn;
        }
    }

    long long q,x,y;
    cin>>q;

    long long res=0;
    for(long long i=0;i<q;i++)
    {
        cin>>x>>y;
        res+=a[prd(x,y)];

        sm[prd(x,y)]=1;

        for(long long j=0;j<4;j++)
        {
            if(can_go(x+corx[j],y+cory[j]))
            {
                mas[prd(x,y)].push_back(prd(x+corx[j],y+cory[j]));
                mas[prd(x+corx[j],y+cory[j])].push_back(prd(x,y));
            }
        }
    }

    for(long long i=0;i<n*m;i++)
    {
        if(!vis[i] && sm[i])
        {
            ver.clear();
            kver=0;

            DFS(i);

            if(ver.size()<(3*kver))
            {
                cout<<"No\n";
                return 0;
            }

            sort(ver.begin(),ver.end());
            reverse(ver.begin(),ver.end());

            kver*=3;
            for(long long i=0;i<kver;i++)
            {
                res+=ver[i];
            }
        }
    }

    cout<<res<<"\n";
    return 0;
}

Compilation message (stderr)

covering.cpp: In function 'int main()':
covering.cpp:101:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  101 |             if(ver.size()<(3*kver))
      |                ~~~~~~~~~~^~~~~~~~~

• 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