Submission #2836107


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair

typedef pair<int,ll> iL;


bool check_consistency(int n,int m,vi& u,vi& v,vi& s,
                      vector<vector<ii>>& nxt, ll x0) {
#ifdef DEBUG
    fprintf(stderr, "x0=%lld\n", x0);
#endif
    if (x0 <= 0) return false;

    vector<ll> x(n, -1);
    // x[0] = x0;
    queue<pair<int,ll>> q;
    q.push(cons(0, x0));
    while (!q.empty()) {
        auto t=q.front(); q.pop();
        // cerr<<t<<endl;
        int u=t.first; ll xu=t.second;
        // xu >= 0
        // fprintf(stderr, "u=%d. xu=%lld, x[u]=%lld.\n", u,xu,x[u]);
        if (x[u] == -1) {
            x[u] = xu;
        } else {
            if (x[u] == xu) continue;
            else return false;
        }
        for (ii v_s: nxt[u]) {
            int v=v_s.first, s=v_s.second;
            // fprintf(stderr, "%d -> (%d %d) ; %lld\n", u,v,s,s-xu);
            if (s-xu <= 0) return false;
            q.push(cons(v,s-xu));
        }
    }
    // cerr << "x:" << x << endl;
    // rep(i,n) if (x[i] <= 0) return false;
    return true;
}

ll solve(int n,int m,vi& u,vi& v,vi& s) {
    vector<vector<ii>> nxt(n);
    rep(i,m){
        int u_i=u[i], v_i=v[i], s_i=s[i];
        nxt[u_i].pb(ii(v_i, s_i));
        nxt[v_i].pb(ii(u_i, s_i));
    }

    vector<bool> visited(n, false);
    vector<iL> ab(n);

    queue<pair<int,iL>> q;
    q.push(cons(0,iL(1,0LL)));
    while (!q.empty()) {
        auto t=q.front(); q.pop();

        int ui = t.first; iL c = t.second;

        if (visited[ui]) {
            if (ab[ui].first == c.first) {
                // + +, - -
                if (ab[ui].second == c.second) {
                    // consistent
                    continue;
                } else {
#ifdef DEBUG
                    cerr << "*inconsistent*" << endl;
#endif
                    return 0;
                }
            } else {
                //ax+b = -cx+d
                int denom = ab[ui].first - c.first; // +-2
                ll numer = c.second - ab[ui].second;
                if (numer % denom == 0) {
                    ll x0 = numer / denom;
                    if (check_consistency(n,m, u,v,s, nxt, x0)) {
                        return 1;
                    } else {
                        return 0;
                    }
                } else {
#ifdef DEBUG
                    cerr << "*impossible*" << endl;
#endif
                    return 0;
                }
            }
            continue;
        }
        visited[ui] = true; ab[ui] = c;

        int a = c.first; ll b = c.second;
        for (ii v_s : nxt[ui]) {
            int uj = v_s.first;
            ll s = (ll)v_s.second;
            // u: ax+b
            // u+v = s; v = s-u = s-(ax+b) = -ax + s-b
            q.push(cons(uj,iL(-a,s-b)));
        }
    }
    // cerr << visited << endl;
    rep(i,n) if (!visited[i]) return 0;

#ifdef DEBUG
    cerr << ab << endl;
#endif
    ll xmin = 1, xmax = LLONG_MAX;
    rep(i,n){
        // fprintf(stderr, "[%lld .. %lld]\n", xmin, xmax);
        int a = ab[i].first; ll b = ab[i].second;
        // fprintf(stderr, "%dx + %lld >= 0\n", a, b);
        if (a == 1) {
            // x + b >= 1
            // x >= 1-b
            // fprintf(stderr, "x >= %lld\n", 1-b);
            xmin = max(xmin, 1-b);
        } else if (a == -1) {
            // -x + b >= 1
            // x <= b-1
            // fprintf(stderr, "x <= %lld\n", b-1);
            xmax = min(xmax, b-1);
        }
    }
    // fprintf(stderr, "[%lld .. %lld]\n", xmin, xmax);
    if (xmax < xmin) return 0;
    return xmax - xmin + 1;
}

int main() {
    int n,m;cin>>n>>m;
    vi u(m),v(m),s(m);
    rep(i,m){
        cin>>u[i]>>v[i]>>s[i];
        --u[i]; --v[i];
    }
    cout << solve(n,m, u,v,s) << endl;
    return 0;
}

Submission Info

Submission Time
Task E - + Graph
User naoya_t
Language C++14 (GCC 5.4.1)
Score 600
Code Size 5079 Byte
Status
Exec Time 122 ms
Memory 11636 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sampleNo.txt, samplePath.txt, sampleTri.txt
All 600 / 600 OK_0.txt, OK_1.txt, OK_2.txt, OK_3.txt, OK_4.txt, close_0.txt, close_1.txt, close_2.txt, close_3.txt, close_4.txt, many_0.txt, many_1.txt, many_2.txt, many_3.txt, many_4.txt, many_5.txt, many_6.txt, many_7.txt, max.txt, maxBip.txt, multiple_0.txt, multiple_1.txt, multiple_2.txt, multiple_3.txt, multiple_4.txt, multiple_5.txt, multiple_6.txt, multiple_7.txt, oddLoop.txt, oddLoop_0.txt, oddLoop_1.txt, oddLoop_2.txt, rnd_0.txt, rnd_1.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, rnd_5.txt, rnd_6.txt, rnd_7.txt, rnd_8.txt, rnd_9.txt, sampleNo.txt, samplePath.txt, sampleTri.txt, star.txt, star_0.txt, star_1.txt, unique_0.txt, unique_1.txt, unique_2.txt, unique_3.txt, unique_4.txt, unique_5.txt, unique_6.txt, unique_7.txt, unique_8.txt, unique_9.txt
Case Name Status Exec Time Memory
OK_0.txt 109 ms 11392 KB
OK_1.txt 109 ms 11392 KB
OK_2.txt 112 ms 10708 KB
OK_3.txt 110 ms 11008 KB
OK_4.txt 113 ms 10952 KB
close_0.txt 114 ms 8704 KB
close_1.txt 115 ms 8832 KB
close_2.txt 110 ms 7936 KB
close_3.txt 121 ms 9088 KB
close_4.txt 116 ms 10496 KB
many_0.txt 115 ms 8832 KB
many_1.txt 111 ms 8704 KB
many_2.txt 113 ms 8576 KB
many_3.txt 112 ms 8448 KB
many_4.txt 112 ms 8448 KB
many_5.txt 112 ms 8448 KB
many_6.txt 112 ms 8576 KB
many_7.txt 114 ms 8704 KB
max.txt 95 ms 11264 KB
maxBip.txt 97 ms 4480 KB
multiple_0.txt 116 ms 9984 KB
multiple_1.txt 118 ms 9728 KB
multiple_2.txt 119 ms 9472 KB
multiple_3.txt 116 ms 9472 KB
multiple_4.txt 119 ms 9344 KB
multiple_5.txt 119 ms 9472 KB
multiple_6.txt 118 ms 9472 KB
multiple_7.txt 118 ms 9728 KB
oddLoop.txt 116 ms 8448 KB
oddLoop_0.txt 115 ms 8448 KB
oddLoop_1.txt 70 ms 5504 KB
oddLoop_2.txt 101 ms 7808 KB
rnd_0.txt 115 ms 10624 KB
rnd_1.txt 118 ms 9856 KB
rnd_2.txt 116 ms 10624 KB
rnd_3.txt 115 ms 9344 KB
rnd_4.txt 117 ms 9344 KB
rnd_5.txt 110 ms 7680 KB
rnd_6.txt 122 ms 9728 KB
rnd_7.txt 117 ms 9600 KB
rnd_8.txt 114 ms 9216 KB
rnd_9.txt 99 ms 6016 KB
sampleNo.txt 1 ms 256 KB
samplePath.txt 1 ms 256 KB
sampleTri.txt 1 ms 256 KB
star.txt 110 ms 11636 KB
star_0.txt 110 ms 11636 KB
star_1.txt 111 ms 11636 KB
unique_0.txt 112 ms 8832 KB
unique_1.txt 113 ms 8832 KB
unique_2.txt 115 ms 8832 KB
unique_3.txt 113 ms 8832 KB
unique_4.txt 113 ms 8960 KB
unique_5.txt 112 ms 8832 KB
unique_6.txt 112 ms 8832 KB
unique_7.txt 113 ms 8960 KB
unique_8.txt 113 ms 8832 KB
unique_9.txt 113 ms 8960 KB