Submission #1059529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059529		vjudge1	T-Covering (eJOI19_covering)	C++17	25 / 100	47 ms	16212 KiB

covering

#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
int dx[4]={-1, 0, 1, 0};
int dy[4]={0, 1, 0, -1};
int n, m, k, mn, ans=0;
vector<vector<int>> a, vis;
vector<vector<bool>> ok;
ii b[1000006];
queue<ii> f;
main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    a.resize(n+1);
    vis.resize(n+1);
    ok.resize(n+1);
    for(int i = 1; i <= n; i++)
    {
        a[i].resize(m+1);
        vis[i].resize(m+1);
        ok[i].resize(m+1);
        for(int j = 1; j <= m; j++)
            cin>>a[i][j];
    }
    cin>>k;
    for(int i = 1; i <= k; i++)
        cin>>b[i].fi>>b[i].se, b[i].fi++, b[i].se++, ok[b[i].fi][b[i].se]=1;
    for(int i = 1; i <= k; i++)
    {
        if(vis[b[i].fi][b[i].se])
            continue;
        int cnt[2];
        mn=inf;
        cnt[0]=cnt[1]=0;
        f.push(b[i]);
        while(f.size())
        {
            ii v=f.front();
            vis[v.fi][v.se]=1;
            cnt[ok[v.fi][v.se]]++;
            ans+=a[v.fi][v.se];
            if(!ok[v.fi][v.se])
                mn=min(mn, a[v.fi][v.se]);
            f.pop();
            for(int k = 0; k < 4; k++)
            {
                int x=v.fi+dx[k];
                int y=v.se+dy[k];
                if(x<1 || x>n || y<1 || y>m)
                    continue;
                if(vis[x][y])
                    continue;
                if(!ok[x][y] && !ok[v.fi][v.se])
                    continue;
                f.push({x, y});
            }
        }
        if(cnt[0]<3*cnt[1])
            return cout<<"No", 0;
        if(cnt[0]==3*cnt[1]+1)
            ans-=mn;
    }
    cout<<ans;
}

Compilation message (stderr)

covering.cpp:17:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   17 | main()
      | ^~~~

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