Submission #1501676

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define INF (1LL << 60)
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(a, b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl
using namespace std;

typedef pair<int,int>P;

const int MAX_N = 100005;

vector<int> bx[MAX_N],by[MAX_N];
ll dpx[MAX_N];
ll dpy[MAX_N];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int w,h,q;
    cin >> w >> h >> q;
    int T = 0;
    rep(i,q){
        int a,b,c;
        cin >> a >> b >> c;
        T = max(T,a-1);
        if(b == 0){
            bx[a-1].pb(c-1);
        }else{
            by[a-1].pb(c-1);
        }
    }
    rep(i,w){
        dpx[i] = 0;
    }
    rep(i,h){
        dpy[i] = 0;
    }
    rep(i,T+1){
        sort(all(bx[i]));
        sort(all(by[i]));
        ll mn = INF;
        rep(j,bx[i].size()){
            if(j+1 < (int)bx[i].size() && bx[i][j+1] - bx[i][j] == 1){
                mn = min(mn+1,dpx[bx[i][j]]);
            }else{
                mn = min(mn,dpx[bx[i][j]]);
                dpx[bx[i][j]+1] = min(dpx[bx[i][j]+1],mn+1);
                mn = INF;
            }
        }
        for(int j=(int)bx[i].size()-1;j>=0;j--){
            if(j-1 >= (int)bx[i].size() && bx[i][j] - bx[i][j-1] == 1){
                mn = min(mn+1,dpx[bx[i][j]]);
            }else{
                if(bx[i][j] == 0){
                    mn = INF;
                }else{
                    mn = min(mn,dpx[bx[i][j]]);
                    dpx[bx[i][j]-1] = min(dpx[bx[i][j]-1],mn+1);
                    mn = INF;
                }
            }
        }
        rep(j,by[i].size()){
            if(j+1 < (int)by[i].size() && by[i][j+1] - by[i][j] == 1){
                mn = min(mn+1,dpy[by[i][j]]);
            }else{
                mn = min(mn,dpy[by[i][j]]);
                dpy[by[i][j]+1] = min(dpy[by[i][j]+1],mn+1);
                mn = INF;
            }
        }
        for(int j=(int)by[i].size()-1;j>=0;j--){
            if(j-1 >= (int)by[i].size() && by[i][j] - by[i][j-1] == 1){
                mn = min(mn+1,dpy[by[i][j]]);
            }else{
                if(by[i][j] == 0){
                    mn = INF;
                }else{
                    mn = min(mn,dpy[by[i][j]]);
                    dpy[by[i][j]-1] = min(dpy[by[i][j]-1],mn+1);
                    mn = INF;
                }
            }
        }
        rep(j,bx[i].size()){
            dpx[bx[i][j]] = INF;
        }
        rep(j,by[i].size()){
            dpy[by[i][j]] = INF;
        }
    }
    ll mn1 = INF;
    rep(i,w){
        mn1 = min(mn1,dpx[i]);
    }
    ll mn2 = INF;
    rep(i,h){
        mn2 = min(mn2,dpy[i]);
    }
    if(mn1 + mn2 > (1LL << 40)){
        cout << "-1\n";
    }else{
        cout << mn1 + mn2 << endl;
    }
    return 0;
}

Submission Info

Judge Result