Submission #658726

#	Time	Username	Problem	Language	Result	Execution time	Memory
658726		nolimiya	T-Covering (eJOI19_covering)	C++17	0 / 100	56 ms	102400 KiB

covering

#include <bits/stdc++.h>
#include <math.h>
//in the name of god,aka allah
//**gray sety orz**
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define pi pair<long long , long long>
#define pii pair<long long , pair<long long , long long>>
const int maxm = 1e6 + 100;
const long long mod = 1e9 + 7 ;
typedef long long ll;
ll l,r,mid;
ll n,m;
bool isval(int mid){
    //cout << mid <<" " << mid*mid-mid <<endl;
    if (((mid-1)*mid)/2 < m) return 0;
    return 1;
}
int darage[maxm] , ss , mm;
queue<pi> q;
vector<int> g[maxm] , z[maxm];
bool vis[maxm] , gos[maxm];
set<pi> st;
pi w[maxm];
//ll rw[maxm][maxm];
int k, t;
vector <int> a[maxm];
vector <bool> siv[maxm];
int X[4] = {-1, 0, 1, 0}, Y[4] = {0, 1, 0, -1};
int X2[4] = {-1, 1, 1, -1}, Y2[4] = {1, 1, -1, -1};
int bd[maxm];
inline bool f(int x, int y){ return ((x>=1)&&(y>=1)&&(x<=n)&&(y<=m));} 
int h(int x, int y){ return (x-1)*m+y;}
void wef(int x, int y, int d){
    siv[x][y] = 0;
    mid += a[x][y];
    a[x][y] = -mod;
    for (int i=0; i<4; i++) {
        if (i==d) continue;
        mid += a[x + X[i]][y + Y[i]];
        a[x + X[i]][y + Y[i]] = -mod;
    }
}
void dfs(int v, int p){
    vis[v] = 1;
    int x=(v-1)/m+1, y=(v-1)%m+1;
    for (int i = 0; i < 4; i++) 
        darage[t] = min(a[x+X[i]][y+Y[i]],darage[t]);
    for (int u:g[v]) {
        if (u==p) continue;
        if (!vis[u]) dfs(u,v);
        else if (vis[u]==1) bd[t]++;
    }
    vis[v]=2;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=0; i<n+3; i++) for(int j=0; j<m+3; j++) siv[i].push_back(0) , a[i].push_back(-mod);
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>>a[i][j];
    cin>>k;
    for (int i=1; i<=k; i++){
        cin >>l>>r , l++ , r++;
        siv[l][r] = 1;
    }
    for (int x=1; x<=n; x++){
        for (int y=1; y<=m; y++){
            for (int i = 0; i < 4; i++){
                if (siv[x][y] && siv[x + X[i]][y + Y[i]]){
                    wef(x, y, i) , wef(x+X[i], y+Y[i], (i+2)&3);
                }
                if (siv[x][y] && siv[x + X2[i]][y + Y2[i]]){
                    wef(x, y, i) , wef(x+X2[i], y+Y2[i], (i+2)&3);
                }
            }
        }
    }
    for (int x=1; x<=n; x++) for (int y=1; y<=m; y++){
            if (!siv[x][y]) continue;
            mid+=a[x][y];
            for (int i=0; i<4; i++) mid+=a[x+X[i]][y+Y[i]];
    }
    for (int x=1; x<=n; x++){
        for (int y=1; y<=m; y++){
            for (int i=0; i<2; i++){
                if (f(x+2*X[i], y+2*Y[i]) && siv[x+2*X[i]][y+2*Y[i]] && siv[x][y]) {
                    l=h(x,y) , r=h(x+2*X[i], y+2*Y[i]);
                    mid-=a[x+X[i]][y+Y[i]];
                    g[l].push_back(r);
                    g[r].push_back(l);
                }
            }
        }
    }
    for (int x = 1; x <= n; x++){
        for (int y = 1; y <= m; y++){
            if (!siv[x][y]) continue;
            int v = h(x, y);
            if (vis[v]) continue;
            t++;
            darage[t]=mod;
            dfs(v,v);
            if (bd[t]>1) return cout<<"No",0;
            if (bd[t]==0) mid-=darage[t];
        }
    }
    if (mid<0) return cout<<"No",0;
    cout<<mid;
}

Compilation message (stderr)

covering.cpp:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    5 | #pragma comment(linker, "/stack:200000000")
      |

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