daily pastebin goal
53%
SHARE
TWEET

pizza_verTrung

CooBin Jul 19th, 2018 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define int             long long
  3. using namespace std;
  4.  
  5. void Read(int &val) {
  6.     val = 0; char c;
  7.     do { c = getchar(); } while (!isdigit(c));
  8.     while (isdigit(c)) { val = val * 10 + c - '0'; c = getchar(); }
  9. }
  10. void Write(int type) {
  11.     if (type == -1) {
  12.         putchar('S'); putchar('A'); putchar('D');
  13.     }
  14.     else if (type == 1) {
  15.         putchar('H'); putchar('A'); putchar('P'); putchar('P'); putchar('Y');
  16.     }
  17.     else {
  18.         putchar('S'); putchar('O'); putchar('S'); putchar('O');
  19.     }
  20.     putchar('\n');
  21. }
  22.  
  23. struct data {
  24.     int u, v, w;
  25.     data() {}; data(int u, int v, int w) : u(u), v(v), w(w) {};
  26. };
  27. typedef pair<int, int> ii;
  28.  
  29. const int N = 2e5 + 4, LOG = 20, oo = 1e16;
  30. int n, m;
  31. data Edge[N];
  32. vector<ii> adj[N];
  33.  
  34. int d[3][N];
  35. priority_queue<ii, vector<ii>, greater<ii> > pq;
  36.  
  37. int hei[N], vis[N], par[N][LOG+4], mom[N];
  38. vector<int> Prev[N], Next[N];
  39.  
  40. map<ii, bool> Map;
  41. map<ii, int> cost, Count;
  42.  
  43. void Dijkstra(int id, int Start) {
  44.     for (int i = 1; i <= n; ++i) d[id][i] = oo; d[id][Start] = 0;
  45.     pq.push(ii(0, Start));
  46.     while (pq.size()) {
  47.         int u = pq.top().second, du = pq.top().first; pq.pop();
  48.         if (du != d[id][u]) continue;
  49.         for (int i = 0; i < adj[u].size(); ++i) {
  50.             int v = adj[u][i].second, uv = adj[u][i].first;
  51.             if (d[id][v] > du + uv) {
  52.                 d[id][v] = du + uv; pq.push(ii(d[id][v], v));
  53.                 if (id == 1) { Prev[v].clear(); Prev[v].push_back(u); }
  54.             }
  55.             else if (d[id][v] == du + uv && id == 1) Prev[v].push_back(u);
  56.         }
  57.     }
  58. }
  59.  
  60. int LCA(int u, int v) {
  61.     if (hei[u] < hei[v]) swap(u, v);
  62.     for (int i = LOG; i >= 0; --i)
  63.         if (hei[u] - (1<<i) >= hei[v]) u = par[u][i];
  64.     if (u == v) return u;
  65.     for (int i = LOG; i >= 0; --i)
  66.         if (par[u][i] != 0 && par[v][i] != 0 && par[u][i] != par[v][i]) {
  67.             u = par[u][i]; v = par[v][i];
  68.         }
  69.     return par[u][0];
  70. }
  71.  
  72. void DFS(int u) {
  73.     vis[u]++;
  74.     if (vis[u] == Prev[u].size()) {
  75.         int dad = 0;
  76.         for (int i = 0; i < Prev[u].size(); ++i) {
  77.             int v = Prev[u][i];
  78.             dad = (i == 0) ? v : LCA(dad, v);
  79.         }
  80.         par[u][0] = dad; hei[u] = hei[dad] + 1; mom[u] = dad;
  81.         for (int i = 1; i <= LOG; ++i) par[u][i] = par[par[u][i-1]][i-1];
  82.  
  83.         for (int v : Next[u]) DFS(v);
  84.     }
  85. }
  86.  
  87. void BuildDomTree() {
  88.     for (int v = 1; v <= n; ++v) {
  89.         for (int u : Prev[v]) Next[u].push_back(v);
  90.     }
  91.     Prev[1].push_back(0);
  92.     DFS(1);
  93. }
  94.  
  95. void AnswerQuery() {
  96.     int u = 2;
  97.     while (u != 1) { Map[ii(mom[u], u)] = true; u = mom[u]; }
  98.  
  99.     for (int i = m; i <= m; ++i) {
  100.         int u = Edge[i].u, v = Edge[i].v;
  101.         bool ok = (d[1][u] + d[2][v] + Edge[i].w == d[1][2]);
  102.         if (Map[ii(u, v)] && Edge[i].w > cost[ii(u, v)] && ok) {
  103.             Write(0); continue;
  104.         }
  105.         if (Map[ii(u, v)] && Edge[i].w == cost[ii(u, v)] && Count[ii(u, v)] >= 2 && ok) {
  106.             Write(0); continue;
  107.         }
  108.         if (Map[ii(u, v)] && ok) {
  109.             Write(-1); continue;
  110.         }
  111.         if (d[1][v] + d[2][u] + Edge[i].w < d[1][2]) Write(1);
  112.         else Write(0);
  113.     }
  114. }
  115.  
  116. void sol() {
  117.     for (int i = 1; i <= m; ++i) {
  118.         int u = Edge[i].u, v = Edge[i].v, w = Edge[i].w;
  119.         adj[u].push_back(ii(w, v));
  120.     }
  121.     Dijkstra(1, 1);
  122.  
  123.     for (int i = 1; i <= n; ++i) adj[i].clear();
  124.     for (int i = 1; i <= m; ++i) {
  125.         int u = Edge[i].u, v = Edge[i].v, w = Edge[i].w;
  126.         adj[v].push_back(ii(w, u));
  127.     }
  128.     Dijkstra(2, 2);
  129. //
  130.     BuildDomTree();
  131.     AnswerQuery();
  132. }
  133.  
  134. main() {
  135.     freopen("pizza.in", "r", stdin);
  136.     freopen("pizza.out", "w", stdout);
  137.  
  138.     Read(n); Read(m);
  139.     int u, v, w;
  140.     for (int i = 1; i <= m; ++i) {
  141.         Read(u); Read(v); Read(w);
  142.         Edge[i] = data(u, v, w);
  143.             int tmp = cost[ii(u, v)];
  144.             if (tmp == 0) cost[ii(u, v)] = w, Count[ii(u, v)] = 1;
  145.             else {
  146.                 if (tmp > w) cost[ii(u, v)] = w, Count[ii(u, v)] = 1;
  147.                 else if (tmp == w) Count[ii(u, v)]++;
  148.             }
  149.     }
  150.  
  151.     sol();
  152.  
  153.     return 0;
  154. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top