oj.uz

Submission #210994

# Submission time Handle Problem Language Result Execution time Memory
210994 2020-03-19T05:05:54 Z HNO2 Designated Cities (JOI19_designated_cities) C++17
16 / 100
 547 ms 54240 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=2e5+7;
const int inf=INT_MAX;
const ll inff=1e18;
const ll mod=1e9+7;
#define pii pair<int,int>
#define mkp make_pair
#define F first
#define S second
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define int ll

#ifdef HNO2
#define IOS
#else
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#endif // HNO2

int x[maxn*2],y[maxn*2],w[maxn*2];
int indeg[maxn];
vector <int> G[maxn];

int ans[maxn];
int tmpsum=0;

pii maxx[maxn];

void dfs(int now,int p)
{
    for (int i:G[now])
        if ((x[i]^y[i]^now)!=p)
    {
        ans[1]+=w[i];
        dfs((x[i]^y[i]^now),now);
    }
}

void dfs2(int now,int p)
{
    ans[1]=min(ans[1],tmpsum);
    for (int i:G[now])
        if ((x[i]^y[i]^now)!=p)
    {
        tmpsum-=(w[i]-w[i^1]);
        dfs2((x[i]^y[i]^now),now);
        tmpsum+=(w[i]-w[i^1]);
    }
}

void dfs3(int now,int p)
{
    pair<pii,pii> nowmax=mkp(mkp(-inff,-inff),mkp(-inff,-inff));

    if (sz(G[now])==1)
    {
        maxx[now]=mkp(0,now);
        return;
    }

    for (int i:G[now])
        if ((x[i]^y[i]^now)!=p)
    {
        int I=(x[i]^y[i]^now);
        tmpsum-=(w[i]-w[i^1]);
        dfs3(I,now);

        //renew
        pii nowpair=mkp(maxx[I].F+w[i],maxx[I].S);
        if (nowpair>=nowmax.F) nowmax.S=nowmax.F,nowmax.F=nowpair;
        else if (nowpair>=nowmax.S) nowmax.S=nowpair;
        //

        tmpsum+=(w[i]-w[i^1]);
    }

    if (nowmax.F.F!=-inff&&nowmax.S.F!=-inff)
        ans[2]=min(ans[2],tmpsum-nowmax.F.F-nowmax.S.F);
    maxx[now]=nowmax.F;
}

void dfs4(int now,int p)
{
     for (int i:G[now])
        if ((x[i]^y[i]^now)!=p)
    {
        tmpsum+=w[i];
        dfs4((x[i]^y[i]^now),now);
    }
}

int32_t main()
{
    IOS
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) ans[i]=inff;

    int _=0;
    for (int i=1;i<=n-1;i++)
    {
        int X,Y,Z,W;
        cin>>X>>Y>>Z>>W;
        x[_]=X,y[_]=Y,w[_]=Z;
        x[_^1]=Y,y[_^1]=X,w[_^1]=W;
        G[X].pb(_);
        G[Y].pb(_^1);
        _+=2;
        indeg[X]++;
        indeg[Y]++;
    }
    //1: calculate ans[1]
    ans[1]=0;
    dfs(1,-1);
    tmpsum=ans[1];
    dfs2(1,-1);
    //
    //2: ans[2]
    if (n==2)
    {
        ans[2]=0;
        int q;
        cin>>q;
        while (q--)
        {
            int X;
            cin>>X;
            cout<<ans[X]<<endl;
        }
        return 0;
    }
    for (int i=1;i<=n;i++)
        if (indeg[i]>=2)
        {
            tmpsum=0;
            dfs4(i,-1);
            dfs3(i,-1);
            break;
        }
    //
    //3: using ans[2] to calculate ans[i]
    //
    int q;
    cin>>q;
    while (q--)
    {
        int X;
        cin>>X;
        cout<<ans[X]<<endl;
    }
    //
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Incorrect 7 ms 5120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 392 ms 28152 KB Output is correct
3 Correct 547 ms 45856 KB Output is correct
4 Correct 379 ms 29084 KB Output is correct
5 Correct 393 ms 29168 KB Output is correct
6 Correct 378 ms 31608 KB Output is correct
7 Correct 291 ms 29148 KB Output is correct
8 Correct 501 ms 46456 KB Output is correct
9 Correct 187 ms 29668 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 365 ms 28024 KB Output is correct
3 Correct 522 ms 54240 KB Output is correct
4 Correct 379 ms 33016 KB Output is correct
5 Correct 359 ms 34412 KB Output is correct
6 Correct 395 ms 37240 KB Output is correct
7 Correct 216 ms 34916 KB Output is correct
8 Correct 468 ms 45560 KB Output is correct
9 Correct 188 ms 34660 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Incorrect 7 ms 5120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 392 ms 28152 KB Output is correct
3 Correct 547 ms 45856 KB Output is correct
4 Correct 379 ms 29084 KB Output is correct
5 Correct 393 ms 29168 KB Output is correct
6 Correct 378 ms 31608 KB Output is correct
7 Correct 291 ms 29148 KB Output is correct
8 Correct 501 ms 46456 KB Output is correct
9 Correct 187 ms 29668 KB Output is correct
10 Correct 8 ms 5120 KB Output is correct
11 Correct 365 ms 28024 KB Output is correct
12 Correct 522 ms 54240 KB Output is correct
13 Correct 379 ms 33016 KB Output is correct
14 Correct 359 ms 34412 KB Output is correct
15 Correct 395 ms 37240 KB Output is correct
16 Correct 216 ms 34916 KB Output is correct
17 Correct 468 ms 45560 KB Output is correct
18 Correct 188 ms 34660 KB Output is correct
19 Correct 8 ms 5120 KB Output is correct
20 Incorrect 390 ms 34428 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Incorrect 7 ms 5120 KB Output isn't correct
3 Halted 0 ms 0 KB -