oj.uz

Submission #737870

# Submission time Handle Problem Language Result Execution time Memory
737870 2023-05-07T21:42:32 Z Deepesson Reconstruction Project (JOI22_reconstruction) C++17
42 / 100
 5000 ms 282012 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;
    if(cur2<0){
        left=partes;
    }else if(cur1<0)
        right=partes;
    else{
        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;
        std::sort(queries[i].begin(),queries[i].end());
        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 3 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 4 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 2 ms 5204 KB Output is correct
13 Correct 3 ms 5204 KB Output is correct
14 Correct 2 ms 5204 KB Output is correct
15 Correct 3 ms 5248 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Correct 2 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 3 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 4 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 2 ms 5204 KB Output is correct
13 Correct 3 ms 5204 KB Output is correct
14 Correct 2 ms 5204 KB Output is correct
15 Correct 3 ms 5248 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Correct 2 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 2851 ms 203336 KB Output is correct
21 Correct 2333 ms 192140 KB Output is correct
22 Correct 2479 ms 200428 KB Output is correct
23 Correct 2431 ms 202724 KB Output is correct
24 Correct 2629 ms 203176 KB Output is correct
25 Correct 2758 ms 203388 KB Output is correct
26 Correct 2780 ms 203244 KB Output is correct
27 Correct 2785 ms 203344 KB Output is correct
28 Correct 2725 ms 203252 KB Output is correct
29 Correct 2260 ms 202888 KB Output is correct
30 Correct 2660 ms 203508 KB Output is correct
31 Correct 2660 ms 203324 KB Output is correct
32 Correct 2798 ms 203396 KB Output is correct
33 Correct 3100 ms 203324 KB Output is correct
34 Correct 1885 ms 203140 KB Output is correct
35 Correct 2652 ms 203328 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 5095 ms 223420 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 4 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 2 ms 5204 KB Output is correct
13 Correct 3 ms 5204 KB Output is correct
14 Correct 2 ms 5204 KB Output is correct
15 Correct 3 ms 5248 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Correct 2 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 5062 ms 29988 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 4 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 2 ms 5204 KB Output is correct
13 Correct 3 ms 5204 KB Output is correct
14 Correct 2 ms 5204 KB Output is correct
15 Correct 3 ms 5248 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Correct 2 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 2851 ms 203336 KB Output is correct
21 Correct 2333 ms 192140 KB Output is correct
22 Correct 2479 ms 200428 KB Output is correct
23 Correct 2431 ms 202724 KB Output is correct
24 Correct 2629 ms 203176 KB Output is correct
25 Correct 2758 ms 203388 KB Output is correct
26 Correct 2780 ms 203244 KB Output is correct
27 Correct 2785 ms 203344 KB Output is correct
28 Correct 2725 ms 203252 KB Output is correct
29 Correct 2260 ms 202888 KB Output is correct
30 Correct 2660 ms 203508 KB Output is correct
31 Correct 2660 ms 203324 KB Output is correct
32 Correct 2798 ms 203396 KB Output is correct
33 Correct 3100 ms 203324 KB Output is correct
34 Correct 1885 ms 203140 KB Output is correct
35 Correct 2652 ms 203328 KB Output is correct
36 Correct 4594 ms 204432 KB Output is correct
37 Correct 4128 ms 192264 KB Output is correct
38 Correct 4281 ms 201680 KB Output is correct
39 Correct 4414 ms 204112 KB Output is correct
40 Correct 4514 ms 204424 KB Output is correct
41 Correct 4659 ms 204292 KB Output is correct
42 Correct 4659 ms 204500 KB Output is correct
43 Correct 4664 ms 204448 KB Output is correct
44 Correct 3008 ms 204580 KB Output is correct
45 Correct 2272 ms 217304 KB Output is correct
46 Correct 4705 ms 204576 KB Output is correct
47 Correct 4765 ms 204472 KB Output is correct
48 Correct 4695 ms 204348 KB Output is correct
49 Correct 4647 ms 204332 KB Output is correct
50 Correct 1883 ms 282012 KB Output is correct
51 Correct 3010 ms 206228 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 4 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 2 ms 5204 KB Output is correct
13 Correct 3 ms 5204 KB Output is correct
14 Correct 2 ms 5204 KB Output is correct
15 Correct 3 ms 5248 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Correct 2 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 2851 ms 203336 KB Output is correct
21 Correct 2333 ms 192140 KB Output is correct
22 Correct 2479 ms 200428 KB Output is correct
23 Correct 2431 ms 202724 KB Output is correct
24 Correct 2629 ms 203176 KB Output is correct
25 Correct 2758 ms 203388 KB Output is correct
26 Correct 2780 ms 203244 KB Output is correct
27 Correct 2785 ms 203344 KB Output is correct
28 Correct 2725 ms 203252 KB Output is correct
29 Correct 2260 ms 202888 KB Output is correct
30 Correct 2660 ms 203508 KB Output is correct
31 Correct 2660 ms 203324 KB Output is correct
32 Correct 2798 ms 203396 KB Output is correct
33 Correct 3100 ms 203324 KB Output is correct
34 Correct 1885 ms 203140 KB Output is correct
35 Correct 2652 ms 203328 KB Output is correct
36 Correct 3 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 5095 ms 223420 KB Time limit exceeded
40 Halted 0 ms 0 KB -