제출 #554071

#제출 시각아이디문제언어결과실행 시간메모리
554071QwertyPi공장들 (JOI14_factories)C++14
컴파일 에러
0 ms0 KiB
#include "factories.h" #include "factories.h" #include <bits/stdc++.h> #include <bits/stdc++.h> #define int long long #define int long long #define fi first #define fi first #define se second #define se second #define pb push_back #define pb push_back #define mp make_pair #define mp make_pair using namespace std; using namespace std; typedef pair<int, int> pii; typedef pair<int, int> pii; const int N = 1e4 + 13, L = 20; const int N = 5e5 + 13, L = 20; const int inf = 1LL << 60; const int inf = 1LL << 60; int d[N], p[N], dep[N], sz[N]; int d[N], p[N], dep[N], sz[N]; vector<pii> G[N]; vector<pii> G[N]; int timer = 0, timer2 = 0, op[N * 2], ed[N * 2], op2[N * 2], ed2[N * 2]; int timer = 0, timer2 = 0, op[N * 2], ed[N * 2], op2[N * 2], ed2[N * 2]; int euler[N], euler2[N * 2]; int euler[N], euler2[N * 2]; int st[N][L]; int st[N][L]; int n; int n; void dfs(int v, int par = -1){ void dfs(int v, int par = -1){ euler[timer] = v, op[v] = timer++, sz[v] = 1; euler[timer] = v, op[v] = timer++, sz[v] = 1; euler2[timer2] = v, op2[v] = timer2++; euler2[timer2] = v, op2[v] = timer2++; int out = 0, son = -1; int out = 0, son = -1; for(auto i : G[v]){ for(auto i : G[v]){ if(i.fi != par){ if(i.fi != par){ d[i.fi] = d[v] + i.se; d[i.fi] = d[v] + i.se; p[i.fi] = v; p[i.fi] = v; dep[i.fi] = dep[v] + 1; dep[i.fi] = dep[v] + 1; dfs(i.fi, v); dfs(i.fi, v); euler2[timer2++] = v; euler2[timer2++] = v; out++; son = i.fi; out++; son = i.fi; sz[v] += sz[i.fi]; sz[v] += sz[i.fi]; } } } } ed[v] = timer; ed[v] = timer; ed2[v] = timer2 - 1; ed2[v] = timer2 - 1; } } struct Fenwick{ struct Fenwick{ int bit[N]; int bit[N]; void upd(int p, int v){ void upd(int p, int v){ p++; p++; for(int i = p; i < N; i += i & -i){ for(int i = p; i < N; i += i & -i){ bit[i] += v; bit[i] += v; } } } int qry(int p){ p++; int ret = 0; for(int i = p; i; i -= i & -i){ ret += bit[i]; } return ret; } int qry_pos(int v){ // 1-base, >= 1 int ret = 0, val = 0; for(int j = 19; j >= 0; j--){ if(ret + (1 << j) >= N) continue; if(val + bit[ret + (1 << j)] < v) val += bit[ret + (1 << j)], ret += (1 << j); } return ret; } } c0, c1; void bl(int n){ for(int i = 0; i < n * 2 - 1; i++) st[i][0] = euler2[i]; for(int j = 1; j < 20; j++){ for(int i = 0; i <= n * 2 - 1 - (1 << j); i++){ st[i][j] = dep[st[i][j - 1]] < dep[st[i + (1 << j - 1)][j - 1]] ? st[i][j - 1] : st[i + (1 << j - 1)][j - 1]; } } } int lca(int x, int y){ int a = min(op2[x], op2[y]), b = max(ed2[x], ed2[y]); int l = __lg(b - a + 1); int ret = dep[st[a][l]] < dep[st[b - (1 << l) + 1][l]] ? st[a][l] : st[b - (1 << l) + 1][l]; return ret; } struct state{ int v, dis, colour; bool operator< (const state& o) const{ return v < o.v; } }; vector<state> qry[N]; void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) { n = N; for(int i = 0; i < N - 1; i++){ G[B[i]].pb({A[i], D[i]}); G[A[i]].pb({B[i], D[i]}); } dfs(0); bl(N); } long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) { for(int j = N - 1; j >= 0; j--) qry[j].clear(); for(int j = 0; j < S; j++){ int v = X[j]; qry[dep[v]].pb({v, d[v] - d[v], 0}); } for(int j = 0; j < T; j++){ int v = Y[j]; qry[dep[v]].pb({v, d[v] - d[v], 1}); } for(int j = 0; j < S; j++) c0.upd(op[X[j]], 1); for(int j = 0; j < T; j++) c1.upd(op[Y[j]], 1); int ans = inf; for(j; pq.size();){ j = pq.top(); pq.pop(); in_pq[j] = false; vector<state> tmp; sort(qry[j].begin(), qry[j].end()); for(auto k : qry[j]){ bool used = false; if(tmp.size() >= 1 && tmp.back().v == k.v && tmp.back().colour + k.colour == 1) ans = min(ans, tmp.back().dis + k.dis); if(tmp.size() >= 2 && tmp[tmp.size() - 2].v == k.v && tmp[tmp.size() - 2].colour + k.colour == 1) ans = min(ans, tmp[tmp.size() - 2].dis + k.dis); if(tmp.size() >= 1 && tmp[tmp.size() - 1].v == k.v && tmp[tmp.size() - 1].colour == k.colour){ tmp[tmp.size() - 1].dis = min(tmp[tmp.size() - 1].dis, k.dis); used = true; } if(tmp.size() >= 2 && tmp[tmp.size() - 2].v == k.v && tmp[tmp.size() - 2].colour == k.colour){ tmp[tmp.size() - 2].dis = min(tmp[tmp.size() - 2].dis, k.dis); used = true; } if(!used){ tmp.pb(k); } } if(j > 0){ for(auto k : tmp){ int _lca = 0; if(k.colour){ int l = c0.qry_pos(c0.qry(op[k.v] - 1)), r = c0.qry_pos(c0.qry(op[k.v] + sz[k.v] - 1) + 1); if(l < 0 && r > n - 1) _lca = 0; else if(l < 0 || r > n - 1) _lca = l < 0 ? lca(k.v, euler[r]) : lca(euler[l], k.v); else{ int llca = lca(euler[l], k.v), rlca = lca(k.v, euler[r]); _lca = (dep[llca] > dep[rlca] ? llca : rlca); } }else{ int l = c1.qry_pos(c1.qry(op[k.v] - 1)), r = c1.qry_pos(c1.qry(op[k.v] + sz[k.v] - 1) + 1); if(l < 0 && r > n - 1) _lca = 0; else if(l < 0 || r > n - 1) _lca = l < 0 ? lca(k.v, euler[r]) : lca(euler[l], k.v); else{ int llca = lca(euler[l], k.v), rlca = lca(k.v, euler[r]); _lca = (dep[llca] > dep[rlca] ? llca : rlca); } } if(_lca == k.v) _lca = p[k.v]; if(!in_pq[dep[_lca]]) in_pq[dep[_lca]] = true, qry[dep[_lca]].clear(), pq.push(dep[_lca]); qry[dep[_lca]].pb({_lca, k.dis + d[k.v] - d[_lca], k.colour}); } } } for(int j = 0; j < S; j++) c0.upd(op[X[j]], -1); for(int j = 0; j < T; j++) c1.upd(op[Y[j]], -1); return ans; }

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp:1:25: warning: extra tokens at end of #include directive
    1 | #include "factories.h"  #include "factories.h"
      |                         ^
factories.cpp:2:27: warning: extra tokens at end of #include directive
    2 | #include <bits/stdc++.h>  #include <bits/stdc++.h>
      |                           ^
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:9:14: note: in expansion of macro 'int'
    9 | typedef pair<int, int> pii;  typedef pair<int, int> pii;
      |              ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:9:19: note: in expansion of macro 'int'
    9 | typedef pair<int, int> pii;  typedef pair<int, int> pii;
      |                   ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:9:43: note: in expansion of macro 'int'
    9 | typedef pair<int, int> pii;  typedef pair<int, int> pii;
      |                                           ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:9:48: note: in expansion of macro 'int'
    9 | typedef pair<int, int> pii;  typedef pair<int, int> pii;
      |                                                ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:10:7: note: in expansion of macro 'int'
   10 | const int N = 1e4 + 13, L = 20;  const int N = 5e5 + 13, L = 20;
      |       ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:10:40: note: in expansion of macro 'int'
   10 | const int N = 1e4 + 13, L = 20;  const int N = 5e5 + 13, L = 20;
      |                                        ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:11:7: note: in expansion of macro 'int'
   11 | const int inf = 1LL << 60;  const int inf = 1LL << 60;
      |       ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:11:35: note: in expansion of macro 'int'
   11 | const int inf = 1LL << 60;  const int inf = 1LL << 60;
      |                                   ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:12:1: note: in expansion of macro 'int'
   12 | int d[N], p[N], dep[N], sz[N];  int d[N], p[N], dep[N], sz[N];
      | ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:12:33: note: in expansion of macro 'int'
   12 | int d[N], p[N], dep[N], sz[N];  int d[N], p[N], dep[N], sz[N];
      |                                 ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:14:1: note: in expansion of macro 'int'
   14 | int timer = 0, timer2 = 0, op[N * 2], ed[N * 2], op2[N * 2], ed2[N * 2];  int timer = 0, timer2 = 0, op[N * 2], ed[N * 2], op2[N * 2], ed2[N * 2];
      | ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:14:75: note: in expansion of macro 'int'
   14 | int timer = 0, timer2 = 0, op[N * 2], ed[N * 2], op2[N * 2], ed2[N * 2];  int timer = 0, timer2 = 0, op[N * 2], ed[N * 2], op2[N * 2], ed2[N * 2];
      |                                                                           ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:15:1: note: in expansion of macro 'int'
   15 | int euler[N], euler2[N * 2];  int euler[N], euler2[N * 2];
      | ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:15:31: note: in expansion of macro 'int'
   15 | int euler[N], euler2[N * 2];  int euler[N], euler2[N * 2];
      |                               ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:16:1: note: in expansion of macro 'int'
   16 | int st[N][L];  int st[N][L];
      | ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:16:16: note: in expansion of macro 'int'
   16 | int st[N][L];  int st[N][L];
      |                ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:17:1: note: in expansion of macro 'int'
   17 | int n;  int n;
      | ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:17:9: note: in expansion of macro 'int'
   17 | int n;  int n;
      |         ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:19:10: note: in expansion of macro 'int'
   19 | void dfs(int v, int par = -1){  void dfs(int v, int par = -1){
      |          ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:19:17: note: in expansion of macro 'int'
   19 | void dfs(int v, int par = -1){  void dfs(int v, int par = -1){
      |                 ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:19:42: note: in expansion of macro 'int'
   19 | void dfs(int v, int par = -1){  void dfs(int v, int par = -1){
      |                                          ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:19:49: note: in expansion of macro 'int'
   19 | void dfs(int v, int par = -1){  void dfs(int v, int par = -1){
      |                                                 ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:22:2: note: in expansion of macro 'int'
   22 |  int out = 0, son = -1;   int out = 0, son = -1;
      |  ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:22:27: note: in expansion of macro 'int'
   22 |  int out = 0, son = -1;   int out = 0, son = -1;
      |                           ^~~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:24:8: note: in expansion of macro 'fi'
   24 |   if(i.fi != par){    if(i.fi != par){
      |        ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:24:28: note: in expansion of macro 'fi'
   24 |   if(i.fi != par){    if(i.fi != par){
      |                            ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:25:8: note: in expansion of macro 'fi'
   25 |    d[i.fi] = d[v] + i.se;     d[i.fi] = d[v] + i.se;
      |        ^~
factories.cpp:5:20: error: stray '#' in program
    5 | #define se second  #define se second
      |                    ^
factories.cpp:25:23: note: in expansion of macro 'se'
   25 |    d[i.fi] = d[v] + i.se;     d[i.fi] = d[v] + i.se;
      |                       ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:25:35: note: in expansion of macro 'fi'
   25 |    d[i.fi] = d[v] + i.se;     d[i.fi] = d[v] + i.se;
      |                                   ^~
factories.cpp:5:20: error: stray '#' in program
    5 | #define se second  #define se second
      |                    ^
factories.cpp:25:50: note: in expansion of macro 'se'
   25 |    d[i.fi] = d[v] + i.se;     d[i.fi] = d[v] + i.se;
      |                                                  ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:26:8: note: in expansion of macro 'fi'
   26 |    p[i.fi] = v;     p[i.fi] = v;
      |        ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:26:25: note: in expansion of macro 'fi'
   26 |    p[i.fi] = v;     p[i.fi] = v;
      |                         ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:27:10: note: in expansion of macro 'fi'
   27 |    dep[i.fi] = dep[v] + 1;     dep[i.fi] = dep[v] + 1;
      |          ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:27:38: note: in expansion of macro 'fi'
   27 |    dep[i.fi] = dep[v] + 1;     dep[i.fi] = dep[v] + 1;
      |                                      ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:28:10: note: in expansion of macro 'fi'
   28 |    dfs(i.fi, v);     dfs(i.fi, v);
      |          ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:28:28: note: in expansion of macro 'fi'
   28 |    dfs(i.fi, v);     dfs(i.fi, v);
      |                            ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:30:19: note: in expansion of macro 'fi'
   30 |    out++; son = i.fi;     out++; son = i.fi;
      |                   ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:30:42: note: in expansion of macro 'fi'
   30 |    out++; son = i.fi;     out++; son = i.fi;
      |                                          ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:31:18: note: in expansion of macro 'fi'
   31 |    sz[v] += sz[i.fi];     sz[v] += sz[i.fi];
      |                  ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:31:41: note: in expansion of macro 'fi'
   31 |    sz[v] += sz[i.fi];     sz[v] += sz[i.fi];
      |                                         ^~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:39:2: note: in expansion of macro 'int'
   39 |  int bit[N];   int bit[N];
      |  ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:39:16: note: in expansion of macro 'int'
   39 |  int bit[N];   int bit[N];
      |                ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:40:11: note: in expansion of macro 'int'
   40 |  void upd(int p, int v){   void upd(int p, int v){
      |           ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:40:18: note: in expansion of macro 'int'
   40 |  void upd(int p, int v){   void upd(int p, int v){
      |                  ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:40:37: note: in expansion of macro 'int'
   40 |  void upd(int p, int v){   void upd(int p, int v){
      |                                     ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:40:44: note: in expansion of macro 'int'
   40 |  void upd(int p, int v){   void upd(int p, int v){
      |                                            ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:42:7: note: in expansion of macro 'int'
   42 |   for(int i = p; i < N; i += i & -i){    for(int i = p; i < N; i += i & -i){
      |       ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:42:46: note: in expansion of macro 'int'
   42 |   for(int i = p; i < N; i += i & -i){    for(int i = p; i < N; i += i & -i){
      |                                              ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:46:2: note: in expansion of macro 'int'
   46 |  int qry(int p){
      |  ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:46:10: note: in expansion of macro 'int'
   46 |  int qry(int p){
      |          ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:48:3: note: in expansion of macro 'int'
   48 |   int ret = 0;
      |   ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:49:7: note: in expansion of macro 'int'
   49 |   for(int i = p; i; i -= i & -i){
      |       ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:55:2: note: in expansion of macro 'int'
   55 |  int qry_pos(int v){ // 1-base, >= 1
      |  ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:55:14: note: in expansion of macro 'int'
   55 |  int qry_pos(int v){ // 1-base, >= 1
      |              ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:56:3: note: in expansion of macro 'int'
   56 |   int ret = 0, val = 0;
      |   ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:57:7: note: in expansion of macro 'int'
   57 |   for(int j = 19; j >= 0; j--){
      |       ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:65:9: note: in expansion of macro 'int'
   65 | void bl(int n){
      |         ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:66:6: note: in expansion of macro 'int'
   66 |  for(int i = 0; i < n * 2 - 1; i++) st[i][0] = euler2[i];
      |      ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:67:6: note: in expansion of macro 'int'
   67 |  for(int j = 1; j < 20; j++){
      |      ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:68:7: note: in expansion of macro 'int'
   68 |   for(int i = 0; i <= n * 2 - 1 - (1 << j); i++){
      |       ^~~
factories.cpp:3:24: error: stray '#' in program