Submission #301675

#	Time	Username	Problem	Language	Result	Execution time	Memory
301675		Nodir_Bobiev	Aesthetic (NOI20_aesthetic)	C++17	100 / 100	835 ms	83668 KiB

Aesthetic

    #include <cstdio>
    #include <queue>
    #include <cstring>
    #define pii pair<long long, int>
    using namespace std;
     
    int N, M;
    vector<pii> adj[300005];
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    long long dist[2][300005];
    int U[300005], V[300005];
    bool can[300005], ada[300005];
    long long W[300005], best[300005];
    vector<pair<int, int>> adj2[300005];
    int disc[300005], low[300005], waktu, need;
    long long p1[300005], p2[300005], pp1[300005], pp2[300005];
    bool ok;
     
    void BFS(int id, int st) {
      memset(ada, 0, sizeof(ada));
      pq.emplace(0LL, st);
      dist[id][st] = 0;
      int u, v;
      long long len, w;
      while(!pq.empty()) {
        u = pq.top().second;
        len = pq.top().first;
        pq.pop();
        if(len != dist[id][u]) continue;
        for(pii now : adj[u]) {
          v = now.second;
          w = now.first;
          if(dist[id][v] > len + w) {
            dist[id][v] = len + w;
            pq.emplace(dist[id][v], v);
          }
        }
      }
    }
     
    void DFS(int u, int p) {
      disc[u] = low[u] = ++waktu;
      int v, id;
      for(pair<int, int> now : adj2[u]) {
        id = now.second;
        if(ada[id] == 0) continue;
        v = now.first; 
        if(disc[v] <= need) {
          DFS(v, u);
          if(low[v] > disc[u] && can[id] && disc[N] >= disc[v]) {
            ok = 1;
          }else low[u] = min(low[u], low[v]);
        }else if(p != v) {
          low[u] = min(low[u], disc[v]);
        }
      }
    }
     
    bool check(long long now) {
      ok = 0;
      need = waktu;
      for(int i = 1; i <= M; i++) {
        if(p1[i] > now && p2[i] > now) ada[i] = 0;
        else ada[i] = 1;
        if(pp1[i] > now && pp2[i] > now) can[i] = 1;
        else can[i] = 0;
      }
      DFS(1, 0);
      if(disc[N] <= need) return 1;
      if(ok) return 1;
      return 0;
    }
     
    int main() {
      memset(dist, 0x3f3f3f3f, sizeof(dist));
      scanf("%d %d", &N, &M);
      int u, v;
      long long w;
      for(int i = 1; i <= M; i++) {
        scanf("%d %d %lld", &u, &v, &w);
        U[i] = u, V[i] = v, W[i] = w;
        adj[u].emplace_back(w, v);
        adj[v].emplace_back(w, u);
        adj2[u].emplace_back(v, i);
        adj2[v].emplace_back(u, i);
      }
      for(int i = M - 1; i > 0; i--) {
        best[i] = max(best[i + 1], W[i + 1]);
      }
      BFS(0, 1);
      BFS(1, N);
      for(int i = 1; i <= M; i++) {
        p1[i] = dist[0][U[i]] + W[i] + dist[1][V[i]];
        p2[i] = dist[0][V[i]] + W[i] + dist[1][U[i]];
        pp1[i] = dist[0][U[i]] + best[i] + W[i] + dist[1][V[i]];
        pp2[i] = dist[0][V[i]] + best[i] + W[i] + dist[1][U[i]];
      }
      long long l = dist[0][N], r = dist[0][N] + best[1], res = dist[0][N], mid;
      while(l <= r) {
        mid = (l + r) >> 1;
        if(check(mid)) {
          l = mid + 1;
          res = l;
        }else r = mid - 1;
      }
      printf("%lld\n", res);
    }

Compilation message (stderr)

Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:76:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |       scanf("%d %d", &N, &M);
      |       ~~~~~^~~~~~~~~~~~~~~~~
Aesthetic.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |         scanf("%d %d %lld", &u, &v, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• 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