oj.uz

Submission #574215

# Submission time Handle Problem Language Result Execution time Memory
574215 2022-06-08T07:48:17 Z groshi Factories (JOI14_factories) C++17
100 / 100
 6408 ms 280080 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include "factories.h"
using namespace std;
struct wi{
    vector<long long> Q;
    vector<long long> nowy;
    int pre=0,post=0;
    int rodzaj=0;
    long long suma[21];
    int t[21];
    int poz=0;
    long long dp[3];
    bool byl=0;
}*w;
vector<pair<int,int> > mam,jedno;
vector<int> pomoc;
int pree=1,postt=1;
void dodaj(int x)
{
    for(int i=1;i<=20;i++)
    {
        w[x].t[i]=w[w[x].t[i-1]].t[i-1];
        w[x].suma[i]=w[x].suma[i-1]+w[w[x].t[i-1]].suma[i-1];
    }
}
void dfs(int x,int ojc)
{
    w[x].pre=pree;
    pree++;
    for(int i=0;i<w[x].Q.size();i+=2)
    {
        int pom=w[x].Q[i];
        if(pom==ojc)
            continue;
        w[pom].t[0]=x;
        w[pom].suma[0]=w[x].Q[i+1];
        w[pom].poz=w[x].poz+1;
        dodaj(pom);
        dfs(pom,x);
    }
    w[x].post=postt;
    postt++;
}
long long wynik=1e18;
void dfs2(int x,int ojc)
{
    //cout<<x<<" "<<ojc<<"\n";
    w[x].dp[1]=1e18;
    w[x].dp[2]=1e18;
    for(int i=0;i<w[x].nowy.size();i+=2)
    {
        int pom=w[x].nowy[i];
        if(pom==ojc)
            continue;
        dfs2(pom,x);
        w[x].dp[1]=min(w[x].dp[1],w[pom].dp[1]+w[x].nowy[i+1]);
        w[x].dp[2]=min(w[x].dp[2],w[pom].dp[2]+w[x].nowy[i+1]);
    }
    w[x].dp[w[x].rodzaj]=0;
    wynik=min(wynik,w[x].dp[1]+w[x].dp[2]);
}
pair<long long,int> lca(int x,int y)
{
    if(w[x].poz>w[y].poz)
        swap(x,y);
    long long wynik=0;
    for(int i=20;i>=0;i--)
    if(w[w[y].t[i]].poz>=w[x].poz)
    {
    wynik+=w[y].suma[i];
    y=w[y].t[i];
    }
    if(x==y)
        return {wynik,x};
    for(int i=20;i>=0;i--)
    if(w[x].t[i]!=w[y].t[i])
    {
        wynik+=w[x].suma[i];
        wynik+=w[y].suma[i];
        x=w[x].t[i];
        y=w[y].t[i];
    }
    if(x==y)
        return {wynik,x};
    else return {wynik+w[x].suma[0]+w[y].suma[0],w[x].t[0]};
}
void Init(int n,int a[],int b[],int c[])
{
    int x,y,z;
    w=new wi[n+3];
    for(int i=1;i<n;i++)
    {
        x=a[i-1];
        y=b[i-1];
        z=c[i-1];
        w[x].Q.push_back(y);
        w[y].Q.push_back(x);
        w[x].Q.push_back(z);
        w[y].Q.push_back(z);
    }
    dfs(0,-1);
}
long long Query(int S,int a[],int T,int b[])
{
    int x;
        wynik=1e18;
        mam.clear();
        pomoc.clear();
        jedno.clear();
        for(int i=1;i<=S;i++)
        {
            x=a[i-1];
            w[x].rodzaj=1;
            jedno.push_back({w[x].pre,x});
            w[x].nowy.clear();
        }
        for(int i=1;i<=T;i++)
        {
            x=b[i-1];
            w[x].rodzaj=2;
            jedno.push_back({w[x].pre,x});
            w[x].nowy.clear();
        }
        sort(jedno.begin(),jedno.end());
        int mam=jedno.size();
        for(int i=0;i<mam-1;i++)///+/-
        {
            pair<long long,int> jest=lca(jedno[i].second,jedno[i+1].second);
            jedno.push_back({w[jest.second].pre,jest.second});
        }
        sort(jedno.begin(),jedno.end());
        pomoc.push_back(jedno[0].second);
        //cout<<"zyje\n";
        w[jedno[0].second].byl=1;
        for(int i=1;i<jedno.size();i++)
        {
            x=jedno[i].second;
            if(w[x].byl==1)
                continue;
            w[x].byl=1;
           // cout<<"mam "<<x<<"\n";
            while(pomoc.size()>0 && w[x].post>w[pomoc.back()].post)
                pomoc.pop_back();
            //if(pomoc.size()==0)
                //cout<<"zle\n";
            //cout<<"krawedz "<<pomoc.back()<<" "<<x<<" ";
            long long odl=lca(pomoc.back(),x).first;
            //cout<<odl<<"\n";
            w[pomoc.back()].nowy.push_back(x);
            w[x].nowy.push_back(pomoc.back());
            w[pomoc.back()].nowy.push_back(odl);
            w[x].nowy.push_back(odl);
            pomoc.push_back(x);
        }
        dfs2(jedno[0].second,-1);
        //cout<<"koniec\n";
        for(int i=0;i<jedno.size();i++)
        {
            w[jedno[i].second].nowy.clear();
            w[jedno[i].second].dp[1]=1e18;
            w[jedno[i].second].dp[2]=1e18;
            w[jedno[i].second].byl=0;
            w[jedno[i].second].rodzaj=0;
        }
        return wynik;
}

Compilation message

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i=0;i<w[x].Q.size();i+=2)
      |                 ~^~~~~~~~~~~~~~
factories.cpp: In function 'void dfs2(int, int)':
factories.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0;i<w[x].nowy.size();i+=2)
      |                 ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:138:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         for(int i=1;i<jedno.size();i++)
      |                     ~^~~~~~~~~~~~~
factories.cpp:160:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |         for(int i=0;i<jedno.size();i++)
      |                     ~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 724 KB Output is correct
2 Correct 1124 ms 10616 KB Output is correct
3 Correct 1259 ms 10612 KB Output is correct
4 Correct 1151 ms 10788 KB Output is correct
5 Correct 1082 ms 20224 KB Output is correct
6 Correct 854 ms 19980 KB Output is correct
7 Correct 1206 ms 20112 KB Output is correct
8 Correct 1161 ms 20168 KB Output is correct
9 Correct 1022 ms 20216 KB Output is correct
10 Correct 797 ms 20048 KB Output is correct
11 Correct 1309 ms 20148 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 1690 ms 225056 KB Output is correct
3 Correct 4027 ms 227576 KB Output is correct
4 Correct 988 ms 240908 KB Output is correct
5 Correct 3535 ms 269520 KB Output is correct
6 Correct 3965 ms 247808 KB Output is correct
7 Correct 3173 ms 68368 KB Output is correct
8 Correct 933 ms 68088 KB Output is correct
9 Correct 3481 ms 72736 KB Output is correct
10 Correct 3291 ms 69884 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 724 KB Output is correct
2 Correct 1124 ms 10616 KB Output is correct
3 Correct 1259 ms 10612 KB Output is correct
4 Correct 1151 ms 10788 KB Output is correct
5 Correct 1082 ms 20224 KB Output is correct
6 Correct 854 ms 19980 KB Output is correct
7 Correct 1206 ms 20112 KB Output is correct
8 Correct 1161 ms 20168 KB Output is correct
9 Correct 1022 ms 20216 KB Output is correct
10 Correct 797 ms 20048 KB Output is correct
11 Correct 1309 ms 20148 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 1690 ms 225056 KB Output is correct
14 Correct 4027 ms 227576 KB Output is correct
15 Correct 988 ms 240908 KB Output is correct
16 Correct 3535 ms 269520 KB Output is correct
17 Correct 3965 ms 247808 KB Output is correct
18 Correct 3173 ms 68368 KB Output is correct
19 Correct 933 ms 68088 KB Output is correct
20 Correct 3481 ms 72736 KB Output is correct
21 Correct 3291 ms 69884 KB Output is correct
22 Correct 3525 ms 260308 KB Output is correct
23 Correct 3088 ms 262036 KB Output is correct
24 Correct 4303 ms 263272 KB Output is correct
25 Correct 4681 ms 266548 KB Output is correct
26 Correct 6194 ms 257480 KB Output is correct
27 Correct 4888 ms 280080 KB Output is correct
28 Correct 1973 ms 255796 KB Output is correct
29 Correct 6408 ms 256280 KB Output is correct
30 Correct 6172 ms 256060 KB Output is correct
31 Correct 6047 ms 256264 KB Output is correct
32 Correct 2556 ms 75032 KB Output is correct
33 Correct 1450 ms 72636 KB Output is correct
34 Correct 2054 ms 67408 KB Output is correct
35 Correct 1991 ms 67200 KB Output is correct
36 Correct 2881 ms 67808 KB Output is correct
37 Correct 2993 ms 67712 KB Output is correct