Submission #626089

#	Time	Username	Problem	Language	Result	Execution time	Memory
626089		Abrar_Al_Samit	Robot (JOI21_ho_t4)	C++17	24 / 100	905 ms	88768 KiB

Main

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

const int MX = 2e5 + 5;
const long long INF = 1e18;

vector<int>g[MX/2];
int cost[MX], color[MX];
int edge[2][MX];
int edgeID[2][MX];
long long cont[MX];
vector<long long>ans[MX/2], sum[MX/2];
vector<bool>vis[MX/2];
map<int,vector<int>>colored_edges[MX/2];
bool atall[MX/2];
map<int,bool>seen[MX/2];


int read(){
  char k = getchar(); int x = 0;
  while(k < '0' || k > '9') k = getchar();
  while(k >= '0' && k <= '9') x = x * 10 + k - '0', k = getchar();
  return x;
}
void PlayGround() {
  int n, m;
  n = read(), m = read();

  for(int i=1, u,v,p,c; i<=m; ++i) {
    u = read(), v = read(), c = read(), p = read();
    g[u].push_back(i);
    g[v].push_back(i);
    color[i] = c, cost[i] = p;
    edge[0][i] = u, edge[1][i] = v;

    edgeID[0][i] = g[u].size();
    edgeID[1][i] = g[v].size();

    colored_edges[u][c].push_back(i);
    colored_edges[v][c].push_back(i);
  }

  for(int i=1; i<=n; ++i) {
    int sz = g[i].size()+1;
    ans[i].resize(sz, INF);
    vis[i].resize(sz, false);
    sum[i].resize(sz, 0LL);
  }

  for(int i=1; i<=n; ++i) {
    int sz = g[i].size();
    for(int j=0; j<sz; ++j) {
      cont[color[g[i][j]]] += cost[g[i][j]];
    }
    for(int j=0; j<sz; ++j) {
      sum[i][j+1] = cont[color[g[i][j]]];
    }
    for(int j=0; j<sz; ++j) {
      cont[color[g[i][j]]] = 0;
    }
  }


  priority_queue<tuple<long long, int, int>>pq;
  pq.emplace(0, 1, 0);
  ans[1][0] = 0;


  while(!pq.empty()) {
    int v = get<1>(pq.top());
    int id = get<2>(pq.top());
    int nerfed = -1;
    if(id) nerfed = g[v][id-1];

    pq.pop();
    if(vis[v][id]) continue;
    vis[v][id] = 1;

    if(atall[v]==0) {
      atall[v] = 1;
      if(nerfed!=-1)  seen[v][color[nerfed]] = 1;

      for(auto e : g[v]) {
        int to = edge[(edge[0][e]==v)][e];
        long long cur = cost[e] + ans[v][id];

        int nextID = edgeID[(edge[0][e]==v)][e];
        int curID = edgeID[(edge[0][e]!=v)][e];

        if(ans[to][nextID]>cur) {
          ans[to][nextID] = cur;
          pq.emplace(-cur, to, nextID);
        }
        cur = sum[v][curID] - cost[e] + ans[v][id];
        if(nerfed!=-1 && color[nerfed]==color[e]) cur -= cost[nerfed];
        if(ans[to][0]>cur) {
          ans[to][0] = cur;
          pq.emplace(-cur, to, 0);
        }
      }
    } else if(nerfed!=-1 && !seen[v].count(color[nerfed])) {
      seen[v][color[nerfed]] = 1;

      for(auto e : colored_edges[v][color[nerfed]]) {
        int to = edge[(edge[0][e]==v)][e];

        int nextID = edgeID[(edge[0][e]==v)][e];
        int curID = edgeID[(edge[0][e]!=v)][e];


        long long cur = sum[v][curID] - cost[e] + ans[v][id];
        if(nerfed!=-1 && color[nerfed]==color[e]) cur -= cost[nerfed];
        if(ans[to][0]>cur) {
          ans[to][0] = cur;
          pq.emplace(-cur, to, 0);
        }
      }

    }
  }



  long long best = INF;
  for(auto b : ans[n]) {
    best = min(b, best);
  }
  if(best==INF) best = -1;
  printf("%lld\n", best);
}
int main() {
  PlayGround();
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void PlayGround()':
Main.cpp:108:13: warning: unused variable 'nextID' [-Wunused-variable]
  108 |         int nextID = edgeID[(edge[0][e]==v)][e];
      |             ^~~~~~

• Subtask 1: 0 / 34
• Subtask 2: 24 / 24
• Subtask 3: 0 / 42