Submission #638588

#	Time	Username	Problem	Language	Result	Execution time	Memory
638588		MMihalev	T-Covering (eJOI19_covering)	C++14	100 / 100	307 ms	56320 KiB

covering

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N=1004004;
bool ok[MAX_N];
int a[MAX_N];
bool used[MAX_N];
int q;
int ans;
int cnt;
int n,m;
vector<int>g[MAX_N];
vector<int>v;
int i,j;
int x,y;
int t,t1,t2,t3,t4;
int tmp;
void Read()
{
    cin>>n>>m;
    tmp=1;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            cin>>a[tmp];
            tmp++;
        }
    }
    cin>>q;

    for(i=1;i<=q;i++)
    {
        cin>>x>>y;
        x++;
        y++;
        t=(x-1)*m+y;
        t1=(x-2)*m+y;
        t2=(x)*m+y;
        t3=(x-1)*m+y-1;
        t4=(x-1)*m+y+1;
        ok[t]=1;
        ans+=a[t];
        if(x>1)
        {
            g[t].push_back(t1);
            g[t1].push_back(t);
        }
        if(x<n)
        {
            g[t].push_back(t2);
            g[t2].push_back(t);
        }
        if(y>1)
        {
            g[t].push_back(t3);
            g[t3].push_back(t);
        }
        if(y<m)
        {
            g[t].push_back(t4);
            g[t4].push_back(t);
        }
    }
}
void DFS(int u)
{
    if(ok[u])cnt++;
    else v.push_back(a[u]);
    used[u]=1;
    for(auto v:g[u])
    {
        if(!used[v])DFS(v);
    }
}
int r;
void Solve()
{
    tmp=1;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(!used[tmp])
            {
                v.clear();
                cnt=0;
                DFS((i-1)*m+j);
                if(3*cnt>v.size())
                {
                    cout<<"No\n";
                    return;
                }
                sort(v.rbegin(),v.rend());
                for(r=0;r<3*cnt;r++)
                {
                    ans+=v[r];
                }
            }
            tmp++;
        }
    }
    cout<<ans<<"\n";
}
int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Read();
    Solve();
    return 0;
}

Compilation message (stderr)

covering.cpp: In function 'void Solve()':
covering.cpp:90:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |                 if(3*cnt>v.size())
      |                    ~~~~~^~~~~~~~~

• 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