Submission #287044

#	Time	Username	Problem	Language	Result	Execution time	Memory
287044		wildturtle	T-Covering (eJOI19_covering)	C++14	25 / 100	450 ms	46584 KiB

covering

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,i,e,f,g,n,m,k,l,A[1000006],B[1000006],fix[1000006],ans;
vector <long long> v1,v[1000006];
void dfs(long long x) {
    if(fix[x]==1) return;
    fix[x]=1;
    if(B[x]==1) l++;
    else v1.push_back(-A[x]);
    for(long long i=0;i<v[x].size();i++) {
        dfs(v[x][i]);
    }
}
int main() {
    cin>>n>>m;
    for(long long i=1;i<=n;i++) {
        for(long long j=1;j<=m;j++) {
            cin>>a;
            A[(i-1)*m+j]=a;
        }
    }
    cin>>k;
    for(long long i=1;i<=k;i++) {
        cin>>a>>b;
        a++; b++;
        B[(a-1)*m+b]=1; ans+=A[(a-1)*m+b];
        if(a>1) {
            v[(a-1)*m+b].push_back((a-2)*m+b);
            v[(a-2)*m+b].push_back((a-1)*m+b);
        }
        if(a<n) {
            v[(a-1)*m+b].push_back(a*m+b);
            v[a*m+b].push_back((a-1)*m+b);
        }
        if(b>1) {
            v[(a-1)*m+b].push_back((a-1)*m+b-1);
            v[(a-1)*m+b-1].push_back((a-1)*m+b);
        }
        if(b<m) {
            v[(a-1)*m+b].push_back((a-1)*m+b+1);
            v[(a-1)*m+b+1].push_back((a-1)*m+b+1);
        }
    }
    for(long long i=1;i<=n*m;i++) {
        if(fix[i]==1) continue;
        v1.clear(); l=0;
        dfs(i);
        if(3*l>v1.size()) { cout<<"NO"; return 0; }
        sort(v1.begin(),v1.end());
        for(long long j=0;j<3*l;j++)
        ans-=v1[j];
    }
    cout<<ans;
}

Compilation message (stderr)

covering.cpp: In function 'void dfs(long long int)':
covering.cpp:10:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(long long i=0;i<v[x].size();i++) {
      |                       ~^~~~~~~~~~~~
covering.cpp: In function 'int main()':
covering.cpp:48:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         if(3*l>v1.size()) { cout<<"NO"; return 0; }
      |            ~~~^~~~~~~~~~

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