oj.uz

Submission #737863

# Submission time Handle Problem Language Result Execution time Memory
737863 2023-05-07T21:23:28 Z Deepesson Reconstruction Project (JOI22_reconstruction) C++17
42 / 100
 5000 ms 284708 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define MAX 505
typedef std::pair<int,int> pii;
typedef std::pair<int,pii> pip;
int pai[MAX],size[MAX];
std::vector<pii> undo,undosz;
void limpa(void){
    for(int i=0;i!=MAX;++i){
        size[i]=1;
        pai[i]=i;
    }
    undo.clear();
    undosz.clear();
}
int find(int a){
    if(pai[a]==a)
        return a;
    return find(pai[a]);
}
void Undo(void){
    if(undo.back().first==-1){
        undo.pop_back();
    }else{
        pai[undo.back().first]=undo.back().second;
        size[undosz.back().first]=undosz.back().second;
        undo.pop_back();
        undosz.pop_back();
    }
}
bool Union(int a,int b){
    a=find(a);
    b=find(b);
    if(a!=b){
        if(size[a]>size[b])std::swap(a,b);
        undo.push_back({a,pai[a]});
        undosz.push_back({b,size[b]});
        pai[a]=b;
        size[b]+=size[a];
        return 1;
    }else undo.push_back({-1,-1});
    return 0;
}
std::vector<pip> con;
using ll = long long;
ll ans[1100000];
std::vector<pii> contratos;
int N,M,Q;
std::vector<int> salva1[105000];
std::vector<pii> queries[105000];
void Dnc(std::vector<pii>& partes,int cur1,int cur2,ll custo,ll delta,int count,ll impacto,ll pos,std::vector<int>& novind,int& i){
    if(count==N-1){
        for(auto&x:partes){
            ans[x.second]=custo+delta*(ll)x.first+impacto*(ll)abs((ll)pos-(ll)x.first);
        }
        return;
    }
    std::vector<pii> left,right;
    for(auto&x:partes){
        if(cur1>=0&&(cur2<0||abs(con[novind[cur1]].first-x.first)<=abs(con[salva1[i][cur2]].first-x.first))){
            left.push_back(x);
        }else {
            right.push_back(x);
        }
    }
    if(left.size()){///Vai para a esquerda
        pip add = con[novind[cur1]];
        ll bonusc=0,bonusd=0,bonuscount=0,impcount=0;
        {
            int c = Union(add.second.first,add.second.second);
            if(c){
                ++bonuscount;
                if(add.first!=pos){
                    bonusc+=add.first;
                    bonusd-=1;
                }else ++impcount;
            }
        }
        Dnc(left,cur1-1,cur2,custo+bonusc,delta+bonusd,count+bonuscount,impacto+impcount,pos,novind,i);
        Undo();
    }

    if(right.size()){
        pip add = con[salva1[i][cur2]];
        ll bonusc=0,bonusd=0,bonuscount=0,impcount=0;
        {
            int c = Union(add.second.first,add.second.second);
            if(c){
                ++bonuscount;
                if(add.first!=pos){
                    bonusc-=add.first;
                    bonusd+=1;
                }else impcount++;
            }
        }
        Dnc(right,cur1,cur2-1,custo+bonusc,delta+bonusd,count+bonuscount,impacto+impcount,pos,novind,i);
        Undo();
    }
}
void simula(void){
    std::vector<int> indices;
    for(int i=0;i!=M;++i){
        indices.push_back(i);
        int count=0;
        std::vector<int> novind;
        limpa();
        for(int j=indices.size()-1;j!=-1;--j){
            const int ref = indices[j];
            const int c = Union(con[ref].second.first,con[ref].second.second);
            if(c){
                ++count;
                novind.push_back(ref);
            }
        }
        std::reverse(novind.begin(),novind.end());
        indices=novind;
        salva1[i]=indices;
    }
    int cur=0;
    for(int i=0;i!=Q;++i){
        const pii ref = contratos[i];
        while((cur+1!=M)&&(abs(ref.first-con[cur].first)>=abs(ref.first-con[cur+1].first))){
            ++cur;
        }
        queries[cur].push_back(ref);
    }
    indices.clear();
    for(int i=M-1;i!=-1;--i){
        indices.push_back(i);
        int count=0;
        std::vector<int> novind;
        limpa();
        for(int j=indices.size()-1;j!=-1;--j){
            const int ref = indices[j];
            const int c = Union(con[ref].second.first,con[ref].second.second);
            if(c){
                ++count;
                novind.push_back(ref);
            }
        }
        std::reverse(novind.begin(),novind.end());
        indices=novind;
        if(queries[i].size())
        {
            limpa();
            Dnc(queries[i],novind.size()-1,salva1[i].size()-1,0,0,0,0,con[i].first,novind,i);
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>N>>M;
    for(int i=0;i!=M;++i){
        int a,b,c;
        std::cin>>a>>b>>c;
        --a;--b;
        con.push_back({c,{a,b}});
    }
    std::sort(con.begin(),con.end());
    std::cin>>Q;
    for(int i=0;i!=Q;++i){
        int x;
        std::cin>>x;
        contratos.push_back({x,i});
    }
    std::sort(contratos.begin(),contratos.end());
    simula();
    for(int i=0;i!=Q;++i){
        std::cout<<ans[i]<<"\n";
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5168 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 3 ms 5204 KB Output is correct
12 Correct 3 ms 5204 KB Output is correct
13 Correct 2 ms 5204 KB Output is correct
14 Correct 2 ms 5204 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Correct 3 ms 5204 KB Output is correct
18 Correct 3 ms 5204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5168 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 3 ms 5204 KB Output is correct
12 Correct 3 ms 5204 KB Output is correct
13 Correct 2 ms 5204 KB Output is correct
14 Correct 2 ms 5204 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Correct 3 ms 5204 KB Output is correct
18 Correct 3 ms 5204 KB Output is correct
19 Correct 3 ms 5204 KB Output is correct
20 Correct 2737 ms 203348 KB Output is correct
21 Correct 2206 ms 192248 KB Output is correct
22 Correct 2318 ms 200428 KB Output is correct
23 Correct 2325 ms 202808 KB Output is correct
24 Correct 2449 ms 203260 KB Output is correct
25 Correct 2577 ms 203328 KB Output is correct
26 Correct 2571 ms 203268 KB Output is correct
27 Correct 2562 ms 203360 KB Output is correct
28 Correct 2552 ms 203492 KB Output is correct
29 Correct 2161 ms 202956 KB Output is correct
30 Correct 2564 ms 203608 KB Output is correct
31 Correct 2551 ms 203272 KB Output is correct
32 Correct 2586 ms 203288 KB Output is correct
33 Correct 2592 ms 203228 KB Output is correct
34 Correct 1766 ms 203364 KB Output is correct
35 Correct 2601 ms 203356 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Execution timed out 5060 ms 223576 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5168 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 3 ms 5204 KB Output is correct
12 Correct 3 ms 5204 KB Output is correct
13 Correct 2 ms 5204 KB Output is correct
14 Correct 2 ms 5204 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Correct 3 ms 5204 KB Output is correct
18 Correct 3 ms 5204 KB Output is correct
19 Correct 3 ms 5204 KB Output is correct
20 Execution timed out 5039 ms 31364 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5168 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 3 ms 5204 KB Output is correct
12 Correct 3 ms 5204 KB Output is correct
13 Correct 2 ms 5204 KB Output is correct
14 Correct 2 ms 5204 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Correct 3 ms 5204 KB Output is correct
18 Correct 3 ms 5204 KB Output is correct
19 Correct 3 ms 5204 KB Output is correct
20 Correct 2737 ms 203348 KB Output is correct
21 Correct 2206 ms 192248 KB Output is correct
22 Correct 2318 ms 200428 KB Output is correct
23 Correct 2325 ms 202808 KB Output is correct
24 Correct 2449 ms 203260 KB Output is correct
25 Correct 2577 ms 203328 KB Output is correct
26 Correct 2571 ms 203268 KB Output is correct
27 Correct 2562 ms 203360 KB Output is correct
28 Correct 2552 ms 203492 KB Output is correct
29 Correct 2161 ms 202956 KB Output is correct
30 Correct 2564 ms 203608 KB Output is correct
31 Correct 2551 ms 203272 KB Output is correct
32 Correct 2586 ms 203288 KB Output is correct
33 Correct 2592 ms 203228 KB Output is correct
34 Correct 1766 ms 203364 KB Output is correct
35 Correct 2601 ms 203356 KB Output is correct
36 Correct 4982 ms 204388 KB Output is correct
37 Correct 4259 ms 192788 KB Output is correct
38 Correct 4327 ms 202268 KB Output is correct
39 Correct 4316 ms 204472 KB Output is correct
40 Correct 4443 ms 204768 KB Output is correct
41 Correct 4551 ms 204844 KB Output is correct
42 Correct 4479 ms 204940 KB Output is correct
43 Correct 4498 ms 204848 KB Output is correct
44 Correct 2953 ms 205076 KB Output is correct
45 Correct 2193 ms 217948 KB Output is correct
46 Correct 4543 ms 205028 KB Output is correct
47 Correct 4492 ms 205000 KB Output is correct
48 Correct 4491 ms 205040 KB Output is correct
49 Correct 4514 ms 205092 KB Output is correct
50 Correct 1855 ms 284708 KB Output is correct
51 Correct 2935 ms 206716 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5168 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 3 ms 5204 KB Output is correct
12 Correct 3 ms 5204 KB Output is correct
13 Correct 2 ms 5204 KB Output is correct
14 Correct 2 ms 5204 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Correct 3 ms 5204 KB Output is correct
18 Correct 3 ms 5204 KB Output is correct
19 Correct 3 ms 5204 KB Output is correct
20 Correct 2737 ms 203348 KB Output is correct
21 Correct 2206 ms 192248 KB Output is correct
22 Correct 2318 ms 200428 KB Output is correct
23 Correct 2325 ms 202808 KB Output is correct
24 Correct 2449 ms 203260 KB Output is correct
25 Correct 2577 ms 203328 KB Output is correct
26 Correct 2571 ms 203268 KB Output is correct
27 Correct 2562 ms 203360 KB Output is correct
28 Correct 2552 ms 203492 KB Output is correct
29 Correct 2161 ms 202956 KB Output is correct
30 Correct 2564 ms 203608 KB Output is correct
31 Correct 2551 ms 203272 KB Output is correct
32 Correct 2586 ms 203288 KB Output is correct
33 Correct 2592 ms 203228 KB Output is correct
34 Correct 1766 ms 203364 KB Output is correct
35 Correct 2601 ms 203356 KB Output is correct
36 Correct 4 ms 5204 KB Output is correct
37 Correct 3 ms 5204 KB Output is correct
38 Correct 3 ms 5204 KB Output is correct
39 Execution timed out 5060 ms 223576 KB Time limit exceeded
40 Halted 0 ms 0 KB -