oj.uz

Submission #805602

# Submission time Handle Problem Language Result Execution time Memory
805602 2023-08-03T18:41:11 Z Essa2006 T-Covering (eJOI19_covering) C++14
5 / 100
 66 ms 23892 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int inf=1e9;
int n, m;
vector<int>Sz, Egs, Mn, P;
vector<vector<int>>A, B;
 
void pre(){
    Sz.clear(), Egs.clear(), Mn.clear(), A.clear(), B.clear();
    Sz.resize((n+1)*(m+2)+1), Egs=P=Sz, Mn.resize((n+1)*(m+2)+1, inf), A.resize(n+2, vector<int>(m+2)), B=A;
    for(int i=1;i<P.size();i++){
        P[i]=i;
    }
}
int trans(int i, int j){
    return i*(m+2)+j;
}
int find(int ind){
    if(ind==P[ind])
        return ind;
    P[ind]=find(P[ind]);
}
 
bool merge(int a, int b){
    int ga=find(a), gb=find(b);
    if(ga==gb)
        return 0;
    if(rand()&1)
        swap(ga, gb);
    P[ga]=gb;
    Sz[gb]+=Sz[ga];
    Mn[gb]=min(Mn[gb], Mn[ga]);
    return 1;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    pre();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>A[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        B[i][0]=B[i][m+1]=1;
    }
    for(int j=1;j<=m;j++){
        B[0][j]=B[n+1][j]=1;
    }
    int q;
    cin>>q;
    while(q--){
        int i, j;
        cin>>i>>j;
        i++, j++;
        B[i][j]+=inf;
        B[i+1][j]++, B[i-1][j]++;
        B[i][j+1]++, B[i][j-1]++;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(B[i][j]<inf)
                continue;
            int cur=trans(i, j);
            if(B[i+1][j]>=inf || B[i-1][j]>=inf || B[i][j-1]>=inf || B[i][j+1]>=inf)
                return cout<<"No", 0;
            Sz[cur]=1;
            if(B[i+1][j]==1)
                Mn[cur]=min(Mn[cur], A[i+1][j]);
            if(B[i-1][j]==1)
                Mn[cur]=min(Mn[cur], A[i-1][j]);
            if(B[i][j+1]==1)
                Mn[cur]=min(Mn[cur], A[i][j+1]);
            if(B[i][j-1]==1)
                Mn[cur]=min(Mn[cur], A[i][j-1]);
        }
    }
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            vector<int>Cur;
            if(i!=n+1 && B[i+1][j]>=inf)
                Cur.push_back(trans(i+1, j));
            if(i && B[i-1][j]>=inf)
                Cur.push_back(trans(i-1, j));
            if(j!=m+1 && B[i][j+1]>=inf)
                Cur.push_back(trans(i, j+1));
            if(j && B[i][j-1]>=inf)
                Cur.push_back(trans(i, j-1));
            for(int l1=0;l1<Cur.size();l1++){
                for(int l2=0;l2<Cur.size();l2++){
                    merge(Cur[l1], Cur[l2]);
                }
            }
        }
    }
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            if(B[i][j]>1 && B[i][j]<inf){
                if(i && B[i-1][j]>=inf)
                    Egs[find(trans(i-1, j))]+=B[i][j]-1;
                else if(i!=n+1 && B[i+1][j]>=inf)
                    Egs[find(trans(i+1, j))]+=B[i][j]-1;
                else if(j && B[i][j-1]>=inf)
                    Egs[find(trans(i, j-1))]+=B[i][j]-1;
                else
                    Egs[find(trans(i, j+1))]+=B[i][j]-1;  
            }
        }
    }
    int ans=0;
    for(int i=0;i<P.size();i++){
        if(i!=find(i))
            continue;
        if(Egs[i]>Sz[i])
            return cout<<"No", 0;
        else if(Egs[i]<=Sz[i]-1){
            ans-=Mn[i];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(B[i][j])
                ans+=A[i][j];
        }
    }
    cout<<ans;
}

Compilation message

covering.cpp: In function 'void pre()':
covering.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=1;i<P.size();i++){
      |                 ~^~~~~~~~~
covering.cpp: In function 'int main()':
covering.cpp:95:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             for(int l1=0;l1<Cur.size();l1++){
      |                          ~~^~~~~~~~~~~
covering.cpp:96:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |                 for(int l2=0;l2<Cur.size();l2++){
      |                              ~~^~~~~~~~~~~
covering.cpp:117:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(int i=0;i<P.size();i++){
      |                 ~^~~~~~~~~
covering.cpp: In function 'int find(int)':
covering.cpp:27:11: warning: control reaches end of non-void function [-Wreturn-type]
   27 |     P[ind]=find(P[ind]);

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 7 ms 2644 KB Output is correct
4 Correct 19 ms 7380 KB Output is correct
5 Correct 66 ms 23892 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 3 ms 984 KB Output is correct
3 Correct 7 ms 2644 KB Output is correct
4 Incorrect 17 ms 7380 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 7 ms 2644 KB Output is correct
4 Correct 19 ms 7380 KB Output is correct
5 Correct 66 ms 23892 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 3 ms 984 KB Output is correct
8 Correct 7 ms 2644 KB Output is correct
9 Incorrect 17 ms 7380 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 7 ms 2644 KB Output is correct
4 Correct 19 ms 7380 KB Output is correct
5 Correct 66 ms 23892 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 3 ms 984 KB Output is correct
8 Correct 7 ms 2644 KB Output is correct
9 Incorrect 17 ms 7380 KB Output isn't correct
10 Halted 0 ms 0 KB -