oj.uz

Submission #726667

# Submission time Handle Problem Language Result Execution time Memory
726667 2023-04-19T08:46:02 Z guagua0407 Factories (JOI14_factories) C++17
100 / 100
 6836 ms 338944 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=5e5+5;
vector<pair<int,int>> adj[mxn];
vector<pair<int,ll>> g[mxn];
ll mn1[mxn],mn2[mxn];
bool visited[mxn];
int sz[mxn];
int n;

int dfs(int v,int p=-1){
    sz[v]=1;
    for(auto u:adj[v]){
        if(u.f==p or visited[u.f]) continue;
        sz[v]+=dfs(u.f,v);
    }
    return sz[v];
}

int find(int v,int mx,int p=-1){
    for(auto u:adj[v]){
        if(u.f==p or visited[u.f]) continue;
        if(sz[u.f]*2>mx) return find(u.f,mx,v);
    }
    return v;
}

void dfs2(int v,int pp,int p=-1,ll d=0){
    g[v].push_back({pp,d});
    for(auto u:adj[v]){
        if(u.f==p or visited[u.f]) continue;
        dfs2(u.f,pp,v,d+u.s);
    }
}

void centroid(int v=0){
    v=find(v,dfs(v));
    dfs2(v,v);
    visited[v]=true;
    for(auto u:adj[v]){
        if(visited[u.f]) continue;
        centroid(u.f);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for(int i=0;i<n;i++){
        int a=A[i];
        int b=B[i];
        int w=D[i];
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
    }
    centroid();
}

long long Query(int S, int X[], int T, int Y[]) {
    for(int i=0;i<S;i++){
        for(auto p:g[X[i]]){
            mn1[p.f]=mn2[p.f]=1e18;
        }
    }
    for(int i=0;i<T;i++){
        for(auto p:g[Y[i]]){
            mn1[p.f]=mn2[p.f]=1e18;
        }
    }
    for(int i=0;i<S;i++){
        for(auto p:g[X[i]]){
            mn1[p.f]=min(mn1[p.f],p.s);
        }
    }
    for(int i=0;i<T;i++){
        for(auto p:g[Y[i]]){
            mn2[p.f]=min(mn2[p.f],p.s);
        }
    }
    ll ans=1e18;
    for(int i=0;i<S;i++){
        for(auto p:g[X[i]]){
            ans=min(ans,mn1[p.f]+mn2[p.f]);
        }
    }
    for(int i=0;i<T;i++){
        for(auto p:g[Y[i]]){
            ans=min(ans,mn1[p.f]+mn2[p.f]);
        }
    }
    return ans;
}

/*int main() {_

    return 0;
}*/
//maybe its multiset not set

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24404 KB Output is correct
2 Correct 483 ms 33896 KB Output is correct
3 Correct 517 ms 34016 KB Output is correct
4 Correct 527 ms 34128 KB Output is correct
5 Correct 561 ms 34192 KB Output is correct
6 Correct 392 ms 33616 KB Output is correct
7 Correct 514 ms 34120 KB Output is correct
8 Correct 537 ms 33996 KB Output is correct
9 Correct 575 ms 34168 KB Output is correct
10 Correct 364 ms 33380 KB Output is correct
11 Correct 558 ms 34200 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24020 KB Output is correct
2 Correct 2873 ms 207264 KB Output is correct
3 Correct 4101 ms 320208 KB Output is correct
4 Correct 1294 ms 137672 KB Output is correct
5 Correct 5404 ms 338944 KB Output is correct
6 Correct 4459 ms 322180 KB Output is correct
7 Correct 1465 ms 85336 KB Output is correct
8 Correct 793 ms 57092 KB Output is correct
9 Correct 1423 ms 93072 KB Output is correct
10 Correct 1523 ms 86756 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24404 KB Output is correct
2 Correct 483 ms 33896 KB Output is correct
3 Correct 517 ms 34016 KB Output is correct
4 Correct 527 ms 34128 KB Output is correct
5 Correct 561 ms 34192 KB Output is correct
6 Correct 392 ms 33616 KB Output is correct
7 Correct 514 ms 34120 KB Output is correct
8 Correct 537 ms 33996 KB Output is correct
9 Correct 575 ms 34168 KB Output is correct
10 Correct 364 ms 33380 KB Output is correct
11 Correct 558 ms 34200 KB Output is correct
12 Correct 16 ms 24020 KB Output is correct
13 Correct 2873 ms 207264 KB Output is correct
14 Correct 4101 ms 320208 KB Output is correct
15 Correct 1294 ms 137672 KB Output is correct
16 Correct 5404 ms 338944 KB Output is correct
17 Correct 4459 ms 322180 KB Output is correct
18 Correct 1465 ms 85336 KB Output is correct
19 Correct 793 ms 57092 KB Output is correct
20 Correct 1423 ms 93072 KB Output is correct
21 Correct 1523 ms 86756 KB Output is correct
22 Correct 4438 ms 208364 KB Output is correct
23 Correct 3874 ms 212464 KB Output is correct
24 Correct 5995 ms 312508 KB Output is correct
25 Correct 5693 ms 316696 KB Output is correct
26 Correct 5266 ms 322156 KB Output is correct
27 Correct 6836 ms 337792 KB Output is correct
28 Correct 2255 ms 140764 KB Output is correct
29 Correct 5177 ms 321928 KB Output is correct
30 Correct 5425 ms 321840 KB Output is correct
31 Correct 5237 ms 321972 KB Output is correct
32 Correct 2147 ms 93184 KB Output is correct
33 Correct 1182 ms 57208 KB Output is correct
34 Correct 1364 ms 67132 KB Output is correct
35 Correct 1377 ms 67236 KB Output is correct
36 Correct 1574 ms 83660 KB Output is correct
37 Correct 1607 ms 83900 KB Output is correct