Submission #1059516

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

covering

#include <bits/stdc++.h>
#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, cur, mn, ans=0;
vector<vector<int>> a, vis;
vector<vector<bool>> ok;
ii b[1000006];
queue<ii> f;
int 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, ans+=a[b[i].fi][b[i].se];
    for(int i = 1; i <= k; i++)
    {
        if(vis[b[i].fi][b[i].se])
            continue;
        int cnt[2];
        cur=0, 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]]++;
            if(!ok[v.fi][v.se])
                cur+=a[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 && !vis[x][y] && ok[x][y]!=ok[v.fi][v.se])
                    f.push({x, y});
            }
        }
        if(cnt[0]<3*cnt[1])
            return cout<<"No", 0;
        if(cnt[0]==3*cnt[1])
            ans+=cur;
        else ans+=cur-mn;
    }
    cout<<ans;
}

• 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