Submission #285127

#	Time	Username	Problem	Language	Result	Execution time	Memory
285127		toloraia	Aesthetic (NOI20_aesthetic)	C++17	0 / 100	468 ms	44012 KiB

Aesthetic

#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
//#define ll __int128
#define ll long long
#define int long long
#define LEFT(a) ((a)<<1)
#define RIGHT(a) (LEFT(a) + 1)
#define MID(a,b) ((a+b)>>1)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define y1 y122

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
/*
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")

#pragma GCC target("avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")

#pragma comment(linker, "/STACK: 20000000005")
*/

using namespace std;

const int N = 300005, INF = 5e14;

int n, m;
int u[N], v[N], x[N], y[N];
int dp[N][2];
bool F[N][2];

vector < pair < int, pair < int, int > > > G[N];

priority_queue < pair < int, pair < int, int > > > Q;

main()
{
    //freopen ("in.in", "r", stdin);freopen ("out.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> u[i] >> v[i] >> x[i];
    }
    for (int i = m; i >= 1; i--){
        y[i] = max (x[i], y[i+1]);
        G[u[i]].pb ({v[i], {x[i], y[i]}});
        G[v[i]].pb ({u[i], {x[i], y[i]}});
    }
    for (int i = 2; i <= n; i++)
        dp[i][0] = dp[i][1] = INF;
    dp[1][0] = 0;
    dp[1][1] = 0;
    Q.push ({0, {1, 0}});
    Q.push ({0, {1, 1}});
    while (Q.size() > 0){
        int k = Q.top().S.F, ch = Q.top().S.S, D;
        Q.pop();
        if (F[k][ch])
            continue;
        F[k][ch] = 1;
        for (auto it : G[k]){
            int to = it.F;
            if (ch == 0){
                D = dp[k][0] + it.S.F;
                if (D < dp[to][0]){
                    dp[to][0] = D;
                    Q.push ({-D, {to, 0}});
                }
            }
            else {
                D = it.S.F + max (dp[k][0] + it.S.S, dp[k][1]);
                if (D < dp[to][1]){
                    dp[to][1] = D;
                    Q.push ({-D, {to, 1}});
                }
            }
        }
    }
    cout << dp[n][0]+1 << endl;
}

Compilation message (stderr)

Aesthetic.cpp:18: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   18 | #pragma GCC optimization ("unroll-loops")
      | 
Aesthetic.cpp:44:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main()
      |      ^

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