Submission #1123905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123905		fern	Aesthetic (NOI20_aesthetic)	C++20	100 / 100	569 ms	101988 KiB

Aesthetic

#include <bits/stdc++.h>
#define f0(i, n) for(int i=0; i<n; i++)
#define f1(i, n) for(int i=1; i<=n; i++)
#define fi first
#define se second
#define pb push_back
#define el cout << "\n";
#define sz(A) (int)A.size()
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOD(i, r, l) for (int i = r; i >= l; i--)
#define all(x) x.begin(), x.end()
#define faster                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                     \
    cout.tie(NULL);
#define AWA signed main()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef unsigned long long ull;
typedef string str;
typedef vector<int> vi;
const int maxn=1000002;
const int mod=1000000007;
const ll inf = 1e18;
#define bit(mask, i) ((mask>>i)&1)
#define lon(x) ((1ll) << (x))
template <class X, class Y>
    bool maximize(X &x, const Y&y)
    {
        if(x<y)
        {
            x=y;
            return true;
        }
        else return false;
    }
template <class X, class Y>
    bool minimize(X &x, const Y&y)
    {
        if(x>y)
        {
            x=y;
            return true;
        }
        else return false;
    }

void file()
{
      #define TASK "INCGRAPH"
    if(fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
}
const int base = 1000000000;
const int base_digits = 9;
struct bigint {
    vector <int> a; int sign;

    bigint() : sign(1) { }
    bigint(long long v) { *this = v; }
    bigint(const string &s) { read(s); }

    void operator = (const bigint &v) { sign = v.sign; a = v.a; }

    void operator = (long long v) {
        sign = 1;
        if (v < 0) sign = -1, v = -v;
        for (; v > 0; v = v / base) a.push_back(v % base);
    }

    bigint operator + (const bigint &v) const {
        if (sign == v.sign) {
            bigint res = v;
            for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
                if (i == (int) res.a.size()) res.a.push_back(0);
                res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
                carry = res.a[i] >= base;
                if (carry) res.a[i] -= base;
            }
            return res;
        }
        return *this - (-v);
    }

    bigint operator - (const bigint &v) const {
        if (sign == v.sign) {
            if (abs() >= v.abs()) {
                bigint res = *this;
                for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
                    res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
                    carry = res.a[i] < 0;
                    if (carry) res.a[i] += base;
                }
                res.trim();
                return res;
            }
            return -(v - *this);
        }
        return *this + (-v);
    }
    void operator *= (int v) {
        if (v < 0) sign = -sign, v = -v;
        for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
            if (i == (int) a.size()) a.push_back(0);
            long long cur = a[i] * (long long) v + carry;
            carry = (int) (cur / base);
            a[i] = (int) (cur % base);
        }
        trim();
    }

    bigint operator * (int v) const {
        bigint res = *this;
        res *= v;
        return res;
    }

    friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
        int norm = base / (b1.a.back() + 1);
        bigint a = a1.abs() * norm;
        bigint b = b1.abs() * norm;
        bigint q, r;
        q.a.resize(a.a.size());

        for (int i = a.a.size() - 1; i >= 0; i--) {
            r *= base;
            r += a.a[i];
            int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
            int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
            int d = ((long long) base * s1 + s2) / b.a.back();
            r -= b * d;
            while (r < 0) r += b, --d;
            q.a[i] = d;
        }

        q.sign = a1.sign * b1.sign;
        r.sign = a1.sign;
        q.trim();
        r.trim();
        return make_pair(q, r / norm);
    }

    bigint operator / (const bigint &v) const { return divmod(*this, v).first;  }
    bigint operator % (const bigint &v) const { return divmod(*this, v).second; }

    void operator /= (int v) {
if (v < 0) sign = -sign, v = -v;
        for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
            long long cur = a[i] + rem * (long long) base;
            a[i] = (int) (cur / v);
            rem = (int) (cur % v);
        }
        trim();
    }

    bigint operator / (int v) const {
        bigint res = *this;
        res /= v;
        return res;
    }

    int operator % (int v) const {
        if (v < 0) v = -v;
        int m = 0;
        for (int i = a.size() - 1; i >= 0; --i)
            m = (a[i] + m * (long long) base) % v;
        return m * sign;
    }

    void operator += (const bigint &v) { *this = *this + v; }
    void operator -= (const bigint &v) { *this = *this - v; }
    void operator *= (const bigint &v) { *this = *this * v; }
    void operator /= (const bigint &v) { *this = *this / v; }

    bool operator < (const bigint& v) const {
        if (sign != v.sign) return sign < v.sign;
        if (a.size() != v.a.size()) return a.size() * sign < v.a.size() * v.sign;
        for (int i = a.size() - 1; i >= 0; i--) if (a[i] != v.a[i])
                return a[i] * sign < v.a[i] * sign;
        return false;
    }

    bool operator >  (const bigint &v) const { return v < *this; }
    bool operator <= (const bigint &v) const { return !(v < *this); }
    bool operator >= (const bigint &v) const { return !(*this < v); }
    bool operator == (const bigint &v) const { return !(*this < v) && !(v < *this); }
    bool operator != (const bigint &v) const { return *this < v || v < *this; }

    void trim() { while (!a.empty() && !a.back()) a.pop_back(); if (a.empty()) sign = 1; }
    bool isZero() const { return a.empty() || (a.size() == 1 && !a[0]); }

    bigint operator - () const { bigint res = *this; res.sign = -sign; return res; }
    bigint abs() const { bigint res = *this; res.sign *= res.sign; return res; }

    long long longValue() const {
        long long res = 0;
        for (int i = a.size() - 1; i >= 0; i--) res = res * base + a[i];
        return res * sign;
    }

    friend bigint gcd(const bigint &a, const bigint &b) { return b.isZero() ? a : gcd(b, a % b); }
    friend bigint lcm(const bigint &a, const bigint &b) { return a / gcd(a, b) * b; }

    void read(const string &s) {
        sign = 1;
        a.clear();
        int pos = 0;
        while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
            if (s[pos] == '-') sign = -sign;
            ++pos;
        }
        for (int i = s.size() - 1; i >= pos; i -= base_digits) {
            int x = 0;
            for (int j = max(pos, i - base_digits + 1); j <= i; j++)
                x = x * 10 + s[j] - '0';
            a.push_back(x);
        }
        trim();
    }

    friend istream& operator >> (istream &stream, bigint &v) {
        string s; stream >> s; v.read(s);
        return stream;
    }

    friend ostream& operator << (ostream &stream, const bigint &v) {
        if (v.sign == -1) stream << '-';
stream << (v.a.empty() ? 0 : v.a.back());
        for (int i = (int) v.a.size() - 2; i >= 0; --i)
            stream << setw(base_digits) << setfill('0') << v.a[i];
        return stream;
    }

    static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
        vector<long long> p(max(old_digits, new_digits) + 1);
        p[0] = 1;
        for (int i = 1; i < (int) p.size(); i++) p[i] = p[i - 1] * 10;
        vector<int> res;
        long long cur = 0;
        int cur_digits = 0;
        for (int i = 0; i < (int) a.size(); i++) {
            cur += a[i] * p[cur_digits];
            cur_digits += old_digits;
            while (cur_digits >= new_digits) {
                res.push_back(int(cur % p[new_digits]));
                cur /= p[new_digits];
                cur_digits -= new_digits;
            }
        }
        res.push_back((int) cur);
        while (!res.empty() && !res.back()) res.pop_back();
        return res;
    }

    static vector <long long> karatsubaMultiply(const vector <long long> &a, const vector <long long> &b) {
        int n = a.size();
        vector <long long> res(n + n);
        if (n <= 32) {
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    res[i + j] += a[i] * b[j];
            return res;
        }

        int k = n >> 1;
        vector <long long> a1(a.begin(), a.begin() + k);
        vector <long long> b1(b.begin(), b.begin() + k);
        vector <long long> a2(a.begin() + k, a.end());
        vector <long long> b2(b.begin() + k, b.end());

        vector <long long> a1b1 = karatsubaMultiply(a1, b1);
        vector <long long> a2b2 = karatsubaMultiply(a2, b2);

        for (int i = 0; i < k; i++) a2[i] += a1[i];
        for (int i = 0; i < k; i++) b2[i] += b1[i];

        vector <long long> r = karatsubaMultiply(a2, b2);

        for (int i = 0; i < (int) a1b1.size(); i++) r[i] -= a1b1[i];
        for (int i = 0; i < (int) a2b2.size(); i++) r[i] -= a2b2[i];
        for (int i = 0; i < (int) r.size(); i++) res[i + k] += r[i];
        for (int i = 0; i < (int) a1b1.size(); i++) res[i] += a1b1[i];
        for (int i = 0; i < (int) a2b2.size(); i++) res[i + n] += a2b2[i];
        return res;
    }

    bigint operator * (const bigint &v) const {
        vector <int> a6 = convert_base(this->a, base_digits, 6);
        vector <int> b6 = convert_base(v.a, base_digits, 6);
        vector <long long> a(a6.begin(), a6.end());
        vector <long long> b(b6.begin(), b6.end());
        while (a.size() < b.size()) a.push_back(0);
        while (b.size() < a.size()) b.push_back(0);
        while (a.size() & (a.size() - 1)) a.push_back(0), b.push_back(0);
        vector <long long> c = karatsubaMultiply(a, b);
        bigint res;
        res.sign = sign * v.sign;
        for (int i = 0, carry = 0; i < (int) c.size(); i++) {
            long long cur = c[i] + carry;
            res.a.push_back((int) (cur % 1000000));
carry = (int) (cur / 1000000);
        }
        res.a = convert_base(res.a, 6, base_digits);
        res.trim();
        return res;
    }

    friend bigint sqrt(const bigint& a) {
        bigint x0 = a, x1 = (a + 1) / 2;
        while (x1 < x0) {
            x0 = x1;
            x1 = (x1 + a / x1) / 2;
        }
        return x0;
    }
    friend bigint pow(bigint a, bigint b) {
        if (b == bigint(0)) return bigint(1);
        bigint T = pow(a, b / 2);
        if (b % 2 == 0) return T * T;
        return T * T * a;
    }

    friend bigint pow(bigint a, int b) { return pow(a, (bigint(b))); }

    friend int log(bigint a, int n) {
        int res = 0;
        while (a > bigint(1)) {
            res++;
            a /= n;
        }
        return res;
    }

    template <class X> friend bigint operator + (const X& v, const bigint& a) { return  a + v; }
    template <class X> friend bigint operator - (const X& v, const bigint& a) { return -a + v; }
    template <class X> friend bigint operator * (const X& v, const bigint& a) { return  a * v; }
    template <class X> friend bigint operator / (const X& v, const bigint& a) { return bigint(v) / a; }

    bigint operator ++() { (*this) += 1; return *this; }
    bigint operator --() { (*this) -= 1; return *this; }
    bigint operator ++(int) { (*this) += 1; return *this - 1; }
    bigint operator --(int) { (*this) -= 1; return *this + 1; }
};
int n, m;
ll eu[maxn], ev[maxn], ew[maxn], Max[maxn];
vector<ii>adj[maxn];
struct Data{
    ll dis[maxn];
    void dijkstra(int s){
        FOR(i, 1, n) dis[i] = inf;
        dis[s] = 0;
        priority_queue<ii, vector<ii>, greater<ii>> pq;
        pq.push(make_pair(dis[s], s));
        while(sz(pq)){
            ii top = pq.top(); pq.pop();
            int dd = top.fi, u = top.se;
            for(ii it: adj[u]){
                int v = it.fi, w = it.se;
                if(dis[v] > dis[u] + w){
                    dis[v] = dis[u] + w;
                    pq.push(make_pair(dis[v], v));
                }
            }
        }
    }
}d1, dn;
struct LINE {
    long long a, b;
    LINE(long long a, long long b) {
        this->a = a;
        this->b = b;
    }
 
    bool operator <(const LINE& otherLine) {
        return a > otherLine.a;
    }
};
 
struct CHT {
    deque <LINE> line;
    bool bad(LINE l1, LINE l2, LINE l3) {
        return (long double) (l3.b - l1.b) / (l1.a - l3.a) <= (long double) (l2.b - l1.b) / (l1.a - l2.a);
    }
 
    long long eval(long long x, LINE line) {
        return line.a * x + line.b;
    }
 
    void addLine(LINE new_line) {
        int n = (int) line.size();
        while (n >= 2 && bad(line[n - 2], line[n - 1], new_line)) {
            line.pop_back();
            n--;
        }
 
        line.push_back(new_line);
    }
 
    long long getValue(long long x) {
        int n = line.size();
        while (n >= 2 && eval(x, line[0]) >= eval(x, line[1])) {
            n--;
            line.pop_front();
        }
 
        return eval(x, line[0]);
    }
} cht;
int low[maxn], num[maxn], timer = 0;
bool contain[maxn];
vector<ii> g[maxn];
bool ok = 0;
void dfs(int s, int pre, ll mid){
    if(s == n) contain[s] = 1;
    low[s] = num[s] = ++timer;
    for(ii it: g[s]){
        int v = it.fi, id = it.se;
        if(id == pre) continue;
        if(!num[v]){
            dfs(v, id, mid); 
            contain[s] |= contain[v];
            low[s] = min(low[s], low[v]);
            if(low[v] == num[v] && contain[v]){
                if(d1.dis[eu[id]] + dn.dis[ev[id]] + ew[id] == d1.dis[n] && d1.dis[eu[id]] + dn.dis[ev[id]] + ew[id] + Max[id] >= d1.dis[n] + mid){
                    ok = 1;
                }
            }
        }
        else low[s] = min(low[s], num[v]);
    }
}
bool check(ll mid){

    FOR(i, 1, n){
        g[i].clear();
        low[i] = num[i] = 0; 
        contain[i] = 0;
    }
    timer = 0; 
    ok = 0;
    f0(i, m){
        ll u = eu[i], v = ev[i], w = ew[i];
        if(d1.dis[u] + dn.dis[v] + ew[i] < d1.dis[n] + mid) 
            g[u].pb(make_pair(v, i)), g[v].pb(make_pair(u, i));
        else if(d1.dis[v] + dn.dis[u] + ew[i] < d1.dis[n] + mid) 
            g[u].pb(make_pair(v, i)), g[v].pb(make_pair(u, i));
    }
    dfs(1, -1, mid);
    return(ok);
}
AWA
{
    faster;
    file();
    cin>>n>>m;
    f0(i, m){
        cin >> eu[i] >> ev[i] >> ew[i];
        adj[eu[i]].pb(make_pair(ev[i], ew[i])); 
        adj[ev[i]].pb(make_pair(eu[i], ew[i]));
    }
    for(int i = m - 2; i >= 0; i--){
        Max[i] = max(Max[i + 1], ew[i + 1]);
    }
    d1.dijkstra(1); 
    dn.dijkstra(n);
    f0(i, m){
        if(d1.dis[eu[i]] > d1.dis[ev[i]]) swap(eu[i], ev[i]);
    }
    ll l = 1, r = *max_element(ew + 1, ew + m + 1), ans = 0;
    while(l <= r){
        ll mid = (l + r) >> 1;
        if(check(mid))
        {
            ans = mid; 
            l = mid + 1;
        }
        else r = mid - 1;
    }

    cout << d1.dis[n] + ans;
    return 0;
}

Compilation message (stderr)

Aesthetic.cpp: In function 'void file()':
Aesthetic.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Aesthetic.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 15 / 15
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22
• Subtask 7: 27 / 27