oj.uz

Submission #659026

# Submission time Handle Problem Language Result Execution time Memory
659026 2022-11-15T21:32:55 Z Soul234 Factories (JOI14_factories) C++14
100 / 100
 3636 ms 158092 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;
}

//void solve() {
////    cin >> N >> Q;
////    F0R(i, N-1) {
////        int u, v, c;
////        cin >> u >> v >> c, u++, v++;
////        adj[u].pb({v, c});
////        adj[v].pb({u, c});
////    }
////    centroid(1, -1, 0);
//
//    while(Q-- > 0) {
//        curtime++;
//        int amtA, amtB;
//        cin >> amtA >> amtB;
//        F0R(i, amtA) {
//            int u; cin >> u, u++;
//            upd(u);
//        }
//        ll ans = INF;
//        F0R(i, amtB) {
//            int u; cin >> u, u++;
//            ckmin(ans, query(u));
//        }
//        cout << ans << nl;
//    }
//}
//
//int main() {
//    setIO();
//
//    int t=1;
//    //cin>>t;
//    while(t-->0) {
//        solve();
//    }
//
//    return 0;
//}

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 235 ms 21160 KB Output is correct
3 Correct 261 ms 21204 KB Output is correct
4 Correct 259 ms 21248 KB Output is correct
5 Correct 276 ms 21432 KB Output is correct
6 Correct 169 ms 21196 KB Output is correct
7 Correct 266 ms 21236 KB Output is correct
8 Correct 276 ms 21200 KB Output is correct
9 Correct 280 ms 21496 KB Output is correct
10 Correct 166 ms 21196 KB Output is correct
11 Correct 261 ms 21156 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12244 KB Output is correct
2 Correct 1506 ms 134152 KB Output is correct
3 Correct 2262 ms 135788 KB Output is correct
4 Correct 561 ms 134704 KB Output is correct
5 Correct 3063 ms 158092 KB Output is correct
6 Correct 2338 ms 136932 KB Output is correct
7 Correct 670 ms 44844 KB Output is correct
8 Correct 299 ms 45484 KB Output is correct
9 Correct 859 ms 48300 KB Output is correct
10 Correct 698 ms 46104 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 235 ms 21160 KB Output is correct
3 Correct 261 ms 21204 KB Output is correct
4 Correct 259 ms 21248 KB Output is correct
5 Correct 276 ms 21432 KB Output is correct
6 Correct 169 ms 21196 KB Output is correct
7 Correct 266 ms 21236 KB Output is correct
8 Correct 276 ms 21200 KB Output is correct
9 Correct 280 ms 21496 KB Output is correct
10 Correct 166 ms 21196 KB Output is correct
11 Correct 261 ms 21156 KB Output is correct
12 Correct 7 ms 12244 KB Output is correct
13 Correct 1506 ms 134152 KB Output is correct
14 Correct 2262 ms 135788 KB Output is correct
15 Correct 561 ms 134704 KB Output is correct
16 Correct 3063 ms 158092 KB Output is correct
17 Correct 2338 ms 136932 KB Output is correct
18 Correct 670 ms 44844 KB Output is correct
19 Correct 299 ms 45484 KB Output is correct
20 Correct 859 ms 48300 KB Output is correct
21 Correct 698 ms 46104 KB Output is correct
22 Correct 1788 ms 135672 KB Output is correct
23 Correct 1810 ms 137968 KB Output is correct
24 Correct 2814 ms 137548 KB Output is correct
25 Correct 2805 ms 140960 KB Output is correct
26 Correct 2729 ms 137608 KB Output is correct
27 Correct 3636 ms 156364 KB Output is correct
28 Correct 680 ms 138672 KB Output is correct
29 Correct 2768 ms 137336 KB Output is correct
30 Correct 2687 ms 136832 KB Output is correct
31 Correct 2754 ms 137408 KB Output is correct
32 Correct 770 ms 49308 KB Output is correct
33 Correct 353 ms 45980 KB Output is correct
34 Correct 492 ms 43004 KB Output is correct
35 Correct 488 ms 43012 KB Output is correct
36 Correct 645 ms 43556 KB Output is correct
37 Correct 706 ms 43548 KB Output is correct