Submission #659026

#	Time	Username	Problem	Language	Result	Execution time	Memory
659026		Soul234	Factories (JOI14_factories)	C++14	100 / 100	3636 ms	158092 KiB

factories

#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 (stderr)

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67