oj.uz

Submission #287044

# Submission time Handle Problem Language Result Execution time Memory
287044 2020-08-31T10:00:17 Z wildturtle T-Covering (eJOI19_covering) C++14
25 / 100
 450 ms 46584 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24064 KB Output is correct
2 Correct 29 ms 24576 KB Output is correct
3 Correct 61 ms 26232 KB Output is correct
4 Correct 164 ms 31096 KB Output is correct
5 Correct 446 ms 46584 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24064 KB Output is correct
2 Incorrect 29 ms 24576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24064 KB Output is correct
2 Correct 29 ms 24568 KB Output is correct
3 Correct 60 ms 26104 KB Output is correct
4 Correct 153 ms 31216 KB Output is correct
5 Correct 450 ms 46552 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 17 ms 23936 KB Output is correct
3 Correct 39 ms 24824 KB Output is correct
4 Correct 31 ms 24568 KB Output is correct
5 Correct 60 ms 25976 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Incorrect 16 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24064 KB Output is correct
2 Correct 29 ms 24576 KB Output is correct
3 Correct 61 ms 26232 KB Output is correct
4 Correct 164 ms 31096 KB Output is correct
5 Correct 446 ms 46584 KB Output is correct
6 Correct 20 ms 24064 KB Output is correct
7 Incorrect 29 ms 24576 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24064 KB Output is correct
2 Correct 29 ms 24576 KB Output is correct
3 Correct 61 ms 26232 KB Output is correct
4 Correct 164 ms 31096 KB Output is correct
5 Correct 446 ms 46584 KB Output is correct
6 Correct 20 ms 24064 KB Output is correct
7 Incorrect 29 ms 24576 KB Output isn't correct
8 Halted 0 ms 0 KB -