oj.uz

Submission #659027

# Submission time Handle Problem Language Result Execution time Memory
659027 2022-11-15T21:34:43 Z Soul234 Factories (JOI14_factories) C++14
100 / 100
 3782 ms 158080 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"
#define fi first
#define se second

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
using db = long double;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

tcT> bool ckmin(T&a, const T&b) {
    return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a=b,1 : 0; }

const int MOD = 1e9 + 7;
const ll INF = 1e18;

const int MX = 5e5+5;
const int LG = 20;

int N, Q;
V<pi> adj[MX];

int sz[MX], lev[MX], cenpar[MX];
bool marked[MX];

ll dist[MX][LG];

void dfsSZ(int u, int p) {
    sz[u] = 1;
    each(ed, adj[u]) if(ed.fi != p && !marked[ed.fi]) {
        dfsSZ(ed.fi, u);
        sz[u] += sz[ed.fi];
    }
}

int findCen(int u, int p, int tot) {
    each(ed, adj[u]) if(ed.fi != p && !marked[ed.fi] && 2*sz[ed.fi] > tot) return findCen(ed.fi, u, tot);
    return u;
}

void dfsDep(int u, int p, int curlev, ll curdist) {
    dist[u][curlev] = curdist;
    each(ed, adj[u]) if(ed.fi != p && !marked[ed.fi]) {
        int v = ed.fi, w = ed.se;
        dfsDep(v, u, curlev, curdist + w);
    }
}

void centroid(int u, int p, int d) {
    dfsSZ(u, -1);
    int cen = findCen(u, -1, sz[u]);
    marked[cen] = 1;
    lev[cen] = d;
    cenpar[cen] = p;
    dfsDep(cen, -1, d, 0);
    each(ed, adj[cen]) if(!marked[ed.fi]) centroid(ed.fi, cen, d+1);
}

int curtime = 0;

ll best[MX];
int lastTime[MX];

void pushTime(int u) {
    if(lastTime[u] != curtime) {
        best[u] = INF;
        lastTime[u] = curtime;
    }
}

void upd(int u) {
    int v = u;
    while(v > 0) {
        pushTime(v);
        ckmin(best[v], dist[u][lev[v]]);
        v = cenpar[v];
    }
}

ll query(int u) {
    int v = u;
    ll res = INF;
    while(v > 0) {
        pushTime(v);
        ckmin(res, best[v] + dist[u][lev[v]]);
        v = cenpar[v];
    }
    return res;
}

void Init(int n, int ver1[], int ver2[], int dis[]) {
    N = n;
    F0R(i, N-1) {
        int u = ver1[i], v = ver2[i], c = dis[i];
        u++, v++;
        adj[u].pb({v, c});
        adj[v].pb({u, c});
    }
    centroid(1, -1, 0);
}

ll Query(int amtA, int verA[], int amtB, int verB[]) {
    curtime++;
    F0R(i, amtA) {
        upd(verA[i]+1);
    }
    ll ans = INF;
    F0R(i, amtB) {
        ckmin(ans, query(verB[i]+1));
    }
    return ans;
}

Compilation message

factories.cpp: In function 'void setIO(std::string)':
factories.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12500 KB Output is correct
2 Correct 269 ms 21208 KB Output is correct
3 Correct 271 ms 21208 KB Output is correct
4 Correct 265 ms 21196 KB Output is correct
5 Correct 294 ms 21512 KB Output is correct
6 Correct 212 ms 21196 KB Output is correct
7 Correct 266 ms 21200 KB Output is correct
8 Correct 313 ms 21320 KB Output is correct
9 Correct 281 ms 21420 KB Output is correct
10 Correct 182 ms 21336 KB Output is correct
11 Correct 302 ms 21192 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 1558 ms 134032 KB Output is correct
3 Correct 2465 ms 135484 KB Output is correct
4 Correct 572 ms 134680 KB Output is correct
5 Correct 3222 ms 158080 KB Output is correct
6 Correct 2504 ms 136920 KB Output is correct
7 Correct 667 ms 44848 KB Output is correct
8 Correct 311 ms 45504 KB Output is correct
9 Correct 838 ms 48260 KB Output is correct
10 Correct 781 ms 46128 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12500 KB Output is correct
2 Correct 269 ms 21208 KB Output is correct
3 Correct 271 ms 21208 KB Output is correct
4 Correct 265 ms 21196 KB Output is correct
5 Correct 294 ms 21512 KB Output is correct
6 Correct 212 ms 21196 KB Output is correct
7 Correct 266 ms 21200 KB Output is correct
8 Correct 313 ms 21320 KB Output is correct
9 Correct 281 ms 21420 KB Output is correct
10 Correct 182 ms 21336 KB Output is correct
11 Correct 302 ms 21192 KB Output is correct
12 Correct 9 ms 12244 KB Output is correct
13 Correct 1558 ms 134032 KB Output is correct
14 Correct 2465 ms 135484 KB Output is correct
15 Correct 572 ms 134680 KB Output is correct
16 Correct 3222 ms 158080 KB Output is correct
17 Correct 2504 ms 136920 KB Output is correct
18 Correct 667 ms 44848 KB Output is correct
19 Correct 311 ms 45504 KB Output is correct
20 Correct 838 ms 48260 KB Output is correct
21 Correct 781 ms 46128 KB Output is correct
22 Correct 1698 ms 135532 KB Output is correct
23 Correct 1828 ms 137952 KB Output is correct
24 Correct 2736 ms 137552 KB Output is correct
25 Correct 3003 ms 140968 KB Output is correct
26 Correct 2933 ms 137604 KB Output is correct
27 Correct 3782 ms 156292 KB Output is correct
28 Correct 747 ms 138696 KB Output is correct
29 Correct 2911 ms 137244 KB Output is correct
30 Correct 3070 ms 136796 KB Output is correct
31 Correct 3034 ms 137312 KB Output is correct
32 Correct 874 ms 49248 KB Output is correct
33 Correct 357 ms 46004 KB Output is correct
34 Correct 646 ms 42944 KB Output is correct
35 Correct 542 ms 42936 KB Output is correct
36 Correct 719 ms 43568 KB Output is correct
37 Correct 750 ms 43488 KB Output is correct