Submission #62203

#TimeUsernameProblemLanguageResultExecution timeMemory
62203cki86201Wild Boar (JOI18_wild_boar)C++11
62 / 100
14799 ms413968 KiB
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <memory.h> #include <math.h> #include <assert.h> #include <queue> #include <map> #include <set> #include <string> #include <algorithm> #include <iostream> #include <functional> #include <unordered_map> #include <unordered_set> #include <list> #include <bitset> using namespace std; typedef long long ll; #define Fi first #define Se second #define pb(x) push_back(x) #define szz(x) ((int)(x).size()) #define rep(i, n) for(int i=0;i<n;i++) #define all(x) (x).begin(), (x).end() typedef tuple<int, int, int> t3; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef long double ldouble; typedef pair<ll, int> pli; int N, M, T, L; t3 edgen[4040]; int edgec[2020][2020]; vector <pii> IE[2020]; vector <int> nume[2020]; vector <int> numl[2020], numr[2020]; vector <pii> E[20020]; int cs; void addedge(int x, int y, int c) { E[x].pb(pii(c, y)); } ll dis[4040][4040], dtemp[12020]; int X[100010]; pii query[100010]; pll tmn[4040][2020][2]; typedef pair<ll, pii> plp; void updplp(plp &a, plp &b) { if(a.Fi > b.Fi) a = b; else if(a.Fi == b.Fi) { a.Se.Fi = min(a.Se.Fi, b.Se.Fi); a.Se.Se = min(a.Se.Se, b.Se.Se); } } ll Val[2020][2020][4][4]; int Idx_l[2020][2020][4]; int Idx_r[2020][2020][4]; int main() { memset(edgec, -1, sizeof edgec); scanf("%d%d%d%d", &N, &M, &T, &L); rep(i, M) { int x, y, z; scanf("%d%d%d", &x, &y, &z); edgen[i<<1] = t3(x, y, z); edgec[x][y] = i<<1; edgen[i<<1|1] = t3(y, x, z); edgec[y][x] = i<<1|1; nume[x].pb(cs++); nume[y].pb(cs++); IE[x].pb(pii(z, y)); IE[y].pb(pii(z, x)); } for(int i=1;i<=N;i++) { int l = szz(IE[i]); numl[i].resize(l); numr[i].resize(l); rep(j, l) numl[i][j] = cs++; rep(j, l) numr[i][j] = cs++; for(int j=1;j<l;j++) { int x = numl[i][j-1], y = numl[i][j]; addedge(y, x, 0); x = numr[i][j-1], y = numr[i][j]; addedge(x, y, 0); } rep(j, l) { addedge(numl[i][j], nume[i][j], 0); addedge(numr[i][j], nume[i][j], 0); } rep(j, l) { int x = nume[i][j] ^ 1, len = get<2>(edgen[x]); if(j) addedge(x, numl[i][j-1], len); if(j < l-1) addedge(x, numr[i][j+1], len); } } rep(st, 2*M) { rep(i, cs) dtemp[i] = 1e18; dtemp[st] = 0; priority_queue <pli, vector<pli>, greater<pli> > pq; pq.push(pli(0, st)); while(!pq.empty()) { pli t = pq.top(); pq.pop(); if(dtemp[t.Se] != t.Fi) continue; for(pii e : E[t.Se]) { if(t.Fi + e.Fi < dtemp[e.Se]) { dtemp[e.Se] = t.Fi + e.Fi; pq.push(pli(dtemp[e.Se], e.Se)); } } } rep(i, 2*M) dis[st][i] = dtemp[i]; } rep(i, 4040) rep(j, 2020) rep(k, 2) tmn[i][j][k] = pll(1e18, -1); for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) { int si = szz(IE[i]); int sj = szz(IE[j]); vector <vector <plp> > mn[4]; rep(a, 4) { mn[a].resize(si); rep(b, si) mn[a][b].resize(sj); } rep(k, si) { int eidx = nume[i][k]; rep(l, sj) { int fidx = nume[j][l] ^ 1; plp pp = plp(dis[eidx][fidx] + get<2>(edgen[fidx]), pii(k, l)); rep(t, 4) mn[t][k][l] = pp; pll p = pll(dis[eidx][fidx] + get<2>(edgen[fidx]), get<0>(edgen[fidx])); if(tmn[eidx][j][0] > p) tmn[eidx][j][1] = tmn[eidx][j][0], tmn[eidx][j][0] = p; else if(tmn[eidx][j][1] > p) tmn[eidx][j][1] = p; } } rep(k, si) for(int l=1;l<sj;l++) for(int a : {0, 2}) updplp(mn[a][k][l], mn[a][k][l-1]); rep(k, si) for(int l=sj-2;l>=0;l--) for(int a : {1, 3}) updplp(mn[a][k][l], mn[a][k][l+1]); rep(l, sj) for(int k=1;k<si;k++) for(int a : {0, 1}) updplp(mn[a][k][l], mn[a][k-1][l]); rep(l, sj) for(int k=si-2;k>=0;k--) for(int a : {2, 3}) updplp(mn[a][k][l], mn[a][k+1][l]); set <int> idx_i, idx_j; rep(k, si) rep(l, sj) { plp r = plp(1e18, pii(-1, -1)); if(k > 0 && l > 0) updplp(r, mn[0][k-1][l-1]); if(k > 0 && l < sj - 1) updplp(r, mn[1][k-1][l+1]); if(k < si - 1 && l > 0) updplp(r, mn[2][k+1][l-1]); if(k < si - 1 && l < sj - 1) updplp(r, mn[3][k+1][l+1]); idx_i.insert(r.Se.Fi); idx_j.insert(r.Se.Se); } if(szz(idx_i) > 4 || szz(idx_j) > 4) { return 0; } } for(int i=1;i<=L;i++) scanf("%d", X+i); for(int i=1;i<=T;i++) { int x, y; scanf("%d%d", &x, &y); query[i] = pii(x, y); } if(T > 1) return 0; X[query[1].Fi] = query[1].Se; int ST = X[1]; ll dp[2020] = {}, tdp[2020]; for(int i=1;i<=N;i++) dp[i] = 1e18; for(int i=1;i<=N;i++) { if(edgec[ST][i] != -1) dp[i] = 0; } for(int i=2;i<=L;i++) { int pre = X[i-1], nxt = X[i]; for(int j=1;j<=N;j++) tdp[j] = 1e18; for(int j=1;j<=N;j++) if(dp[j] < 1e18) { int eidx = edgec[pre][j]; rep(u, 2) if(tmn[eidx][nxt][u].Fi < 1e18) { int fj = (int)tmn[eidx][nxt][u].Se; tdp[fj] = min(tdp[fj], dp[j] + tmn[eidx][nxt][u].Fi); } } if(i == L) break; pll wp[2]; rep(u, 2) wp[u] = pll(1e18, -1); for(int j=1;j<=N;j++) { pll p = pll(tdp[j], j); if(wp[0] > p) wp[1] = wp[0], wp[0] = p; else if(wp[1] > p) wp[1] = p; } for(int j=1;j<=N;j++) { if(edgec[nxt][j] != -1) { if(wp[0].Se != j) dp[j] = wp[0].Fi; else dp[j] = wp[1].Fi; } else dp[j] = 1e18; } } ll ans = 1e18; for(int i=1;i<=N;i++) ans = min(ans, tdp[i]); if(ans == 1e18) puts("-1"); else printf("%lld\n", ans); return 0; }

Compilation message (stderr)

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &N, &M, &T, &L);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &y, &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:164:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=L;i++) scanf("%d", X+i);
                        ~~~~~^~~~~~~~~~~
wild_boar.cpp:166:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...