Submission #413393

#TimeUsernameProblemLanguageResultExecution timeMemory
413393souvenir_vayneFactories (JOI14_factories)C++14
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <chrono> #define pb push_back #define INF 0x3f3f3f3f #define LINF 0x3f3f3f3f3f3f3f3f #define endl '\n' #define ll long long #define f first #define fin cin #define fout cout #define int long long #define s second #define FAST cin.tie(0), cout.tie(0), ios::sync_with_stdio(0) #define debug(x) cout << "DEBUG " << x << endl #define debug2(x, y) cout << "DEBUG " << x << " " << y << endl #define debug3(x, y, z) cout << "DEBUG " << x << " " << y << " " << z<< endl #define debug4(x, y, z, o) cout << "DEBUG " << x << " " << y << " " << z<< " " << o << endl #define all(x) x.begin(), x.end() #define left vadia #define lb lower_bound #define right puta using namespace std; using namespace __gnu_pbds; void setIO(string s) { ios_base::sync_with_stdio(0); cin.tie(0); freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } typedef pair<ll, ll> pii; typedef vector<vector<char>> mat; typedef pair<int, string> pis; const ll mod = 998244353; typedef vector<int> vi; typedef pair<int, pair<int, int>> piii; const int MAXN = 5e5+5; int anc[MAXN][22], al[MAXN], h[MAXN], pai[MAXN], sz[MAXN], used[MAXN], best[MAXN]; vector<pii> g[MAXN]; int getsz(int u, int p) { sz[u] = 1; for(pii &i : g[u]) if(i.f != p && !used[i.f]) sz[u] += getsz(i.f, u); return sz[u]; } int findc(int u, int p, int n) { for(pii &i : g[u]) if(i.f != p && !used[i.f] && sz[i.f] > n/2) return findc(i.f, u, n); return u; } void build(int u, int p) { int c = findc(u, -1, getsz(u, -1)); used[c] = 1; pai[c] = p; for(pii &i : g[c]) if(!used[i.f]) build(i.f, c); } void dfs(int u) { for(pii &i : g[u]) if(i.f != anc[u][0]) { anc[i.f][0] = u; al[i.f] = al[u] + 1; h[i.f] = h[u] + i.s; dfs(i.f); } } int getlca(int a, int b) { if(al[a] < al[b]) swap(a, b); for(int i = 0; i <= 20; i++) if( (1<<i) & (al[b] - al[a]) ) a = anc[a][i]; if(a == b) return a; for(int i = 20; i >= 0; i--) if(anc[a][i] != anc[b][i]) a = anc[a][i], b = anc[b][i]; return anc[a][0]; } int dist(int a, int b) { return h[a] + h[b] - 2*h[getlca(a, b)]; } void update(int u) { int aux = u; while(u != -1) { best[u] = min(best[u], dist(aux, u)); //debug2(u, best[u]); u = pai[u]; } } int query(int u) { int aux = u, ans = LINF; while(u != -1) { ans = min(ans, best[u] + dist(aux, u)); u = pai[u]; } return ans; } void reset(int u) { int aux = u; while(u != -1) { best[u] = LINF; u = pai[u]; } } int32_t main() { int n, q; cin >> n >> q; for(int i = 0; i < n; i++) best[i] = LINF; for(int i = 1; i < n; i++) { int a, b, c; cin >> a >> b >> c; g[a].pb({b, c}); g[b].pb({a, c}); } dfs(0); for(int j = 1; j < 22; j++) for(int i = 1; i <= n; i++) anc[i][j] = anc[anc[i][j-1]][j-1]; build(0, -1); //debug(dist(2, 6)); while(q--) { int s, t; cin >> s >> t; //debug("Mina san"); vector<int> v(s); for(int i = 0; i < s; i++) { int x; cin >> x; v[i] = x; update(x); } int ans = LINF; for(int i = 0; i < t; i++) { int x; cin >> x; ans = min(ans, query(x)); } cout << ans << endl; for(int &i : v) reset(i); } }

Compilation message (stderr)

factories.cpp: In function 'void reset(long long int)':
factories.cpp:118:9: warning: unused variable 'aux' [-Wunused-variable]
  118 |     int aux = u;
      |         ^~~
factories.cpp: In function 'void setIO(std::string)':
factories.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   freopen((s+".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccbxHYSx.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccBtGmkx.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccbxHYSx.o: in function `main':
grader.cpp:(.text.startup+0x37d): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status