oj.uz

Submission #378154

# Submission time Handle Problem Language Result Execution time Memory
378154 2021-03-16T05:27:03 Z daniel920712 Designated Cities (JOI19_designated_cities) C++14
16 / 100
 753 ms 165868 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <set>

using namespace std;
vector < pair < long long , long long > > Next[200005];
map < long long , long long > all[200005];
set < long long > vis[200005];
long long ans[200005];
long long all2[200005];
long long xx[200005];
long long how[200005];
long long who[200005];
long long Father[200005];
long long l,r,now2=0;
long long ll[200005],rr[200005];
long long N=0,big=1e18;
long long x,y,root,now=1;
pair < long long , long long > A,B;
struct A
{
    long long here,l,r,add;
    long long nxl,nxr;
    pair < long long , long long > ans;
}Node[1000005];
void build(long long l,long long r,long long here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].add=0;
    if(l==r)
    {
        Node[here].ans=make_pair(all2[here],here);
        return;
    }
    Node[here].nxl=now++;
    Node[here].nxr=now++;
    build(l,(l+r)/2,Node[here].nxl);
    build((l+r)/2+1,r,Node[here].nxr);
    Node[here].ans=max(Node[Node[here].nxl].ans,Node[Node[here].nxr].ans);
}
void UPD(long long here)
{
    Node[Node[here].nxl].ans.first+=Node[here].add;
    Node[Node[here].nxr].ans.first+=Node[here].add;
    Node[Node[here].nxl].add+=Node[here].add;
    Node[Node[here].nxr].add+=Node[here].add;
    Node[here].add=0;
    return;
}
void cha(long long l,long long r,long long con,long long here)
{
    if(l==Node[here].l&&r==Node[here].r)
    {
        Node[here].ans.first+=con;
        return;
    }
    UPD(here);
    if(r<=(Node[here].l+Node[here].r)/2) cha(l,r,con,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) cha(l,r,con,Node[here].nxr);
    else
    {
        cha(l,(Node[here].l+Node[here].r)/2,con,Node[here].nxl);
        cha((Node[here].l+Node[here].r)/2+1,r,con,Node[here].nxr);
    }
    Node[here].ans=max(Node[Node[here].nxl].ans,Node[Node[here].nxr].ans);
}
void F(long long here,long long fa)
{
    for(auto i:Next[here])
    {
        if(i.first!=fa)
        {
            ans[1]+=i.second;
            F(i.first,here);
        }
    }
}
void F2(long long here,long long fa)
{
    for(auto i:Next[here])
    {
        if(i.first!=fa)
        {
            ans[i.first]=ans[here]-all[here][i.first]+all[i.first][here];
            F2(i.first,here);
        }
    }
}
pair < long long , long long > F4(long long here,long long fa,long long con)
{
    pair < long long , long long > a=make_pair(con,here),b=make_pair(con,here),tt;
    for(auto i:Next[here])
    {
        if(i.first!=fa)
        {
            tt=F4(i.first,here,con+i.second);
            if(tt>a)
            {
                b=a;
                a=tt;
            }
            else if(tt>b) b=tt;
        }
    }
    big=min(big,ans[here]-(a.first+b.first-2*con));
    if(big==ans[here]-(a.first+b.first-2*con))
    {
        root=here;
        x=a.second;
        y=b.second;
    }
    return a;
}
void F3(long long here,long long fa,long long con)
{
    pair < long long , long long > a=make_pair(con,here),tt;
    for(auto i:Next[here]) if(i.first!=fa) F3(i.first,here,con+i.second);
    big=max(big,con);
    if(big==con) x=here;
}
void F5(long long here)
{
    long long ok=0;
    if(Father[here]==-1||all[Father[here]].find(here)==all[Father[here]].end()) return;
    cha(ll[Father[here]],rr[Father[here]],0-all[Father[here]][here],0);
    all[Father[here]].erase(here);
}
void F6(long long here,long long fa,long long con)
{
    all2[now2]=con;
    ll[here]=now2;
    Father[here]=fa;
    //who[now2]=here;
    for(auto i:Next[here])
    {
        if(i.first==fa) continue;
        now2++;
        F6(i.first,here,con+i.second);
    }
    rr[here]=now2;
}
int main()
{
    long long M,i,j,k,a,b,c,d,where;
    scanf("%lld",&N);
    for(i=1;i<N;i++)
    {
        scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
        Next[a].push_back(make_pair(b,c));
        Next[b].push_back(make_pair(a,d));
        all[a][b]=c;
        all[b][a]=d;
    }
    for(i=1;i<=N;i++) xx[i]=1e18;
    F(1,-1);
    F2(1,-1);
    how[1]=1e18;
    for(i=1;i<=N;i++)
    {
        how[1]=min(how[1],ans[i]);
        if(how[1]==ans[i]) where=i;
    }
    F4(1,-1,0);
    F6(root,-1,0);
    build(0,N-1,0);
    F5(x);
    F5(y);
    how[2]=big;
    for(i=3;i<=N;i++)
    {
        x=Node[0].ans.second;
        how[i]=how[i-1]-Node[0].ans.first;
        F5(x);
    }
    scanf("%lld",&M);
    while(M--)
    {
        scanf("%lld",&a);
        printf("%lld\n",how[a]);
    }

    return 0;
}

Compilation message

designated_cities.cpp: In function 'void F3(long long int, long long int, long long int)':
designated_cities.cpp:120:36: warning: variable 'a' set but not used [-Wunused-but-set-variable]
  120 |     pair < long long , long long > a=make_pair(con,here),tt;
      |                                    ^
designated_cities.cpp: In function 'void F5(long long int)':
designated_cities.cpp:127:15: warning: unused variable 'ok' [-Wunused-variable]
  127 |     long long ok=0;
      |               ^~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:148:19: warning: unused variable 'j' [-Wunused-variable]
  148 |     long long M,i,j,k,a,b,c,d,where;
      |                   ^
designated_cities.cpp:148:21: warning: unused variable 'k' [-Wunused-variable]
  148 |     long long M,i,j,k,a,b,c,d,where;
      |                     ^
designated_cities.cpp:148:31: warning: variable 'where' set but not used [-Wunused-but-set-variable]
  148 |     long long M,i,j,k,a,b,c,d,where;
      |                               ^~~~~
designated_cities.cpp:149:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  149 |     scanf("%lld",&N);
      |     ~~~~~^~~~~~~~~~~
designated_cities.cpp:152:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  152 |         scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:179:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  179 |     scanf("%lld",&M);
      |     ~~~~~^~~~~~~~~~~
designated_cities.cpp:182:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  182 |         scanf("%lld",&a);
      |         ~~~~~^~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 86508 KB Output is correct
2 Incorrect 58 ms 86508 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 50 ms 86508 KB Output is correct
2 Correct 615 ms 135992 KB Output is correct
3 Correct 661 ms 158988 KB Output is correct
4 Correct 659 ms 135916 KB Output is correct
5 Correct 663 ms 136128 KB Output is correct
6 Correct 619 ms 139372 KB Output is correct
7 Correct 715 ms 135388 KB Output is correct
8 Correct 656 ms 159856 KB Output is correct
9 Correct 728 ms 135188 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 86528 KB Output is correct
2 Correct 614 ms 135916 KB Output is correct
3 Correct 662 ms 165868 KB Output is correct
4 Correct 634 ms 138044 KB Output is correct
5 Correct 637 ms 139108 KB Output is correct
6 Correct 645 ms 142948 KB Output is correct
7 Correct 729 ms 138196 KB Output is correct
8 Correct 667 ms 154092 KB Output is correct
9 Correct 753 ms 137940 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 86508 KB Output is correct
2 Correct 615 ms 135992 KB Output is correct
3 Correct 661 ms 158988 KB Output is correct
4 Correct 659 ms 135916 KB Output is correct
5 Correct 663 ms 136128 KB Output is correct
6 Correct 619 ms 139372 KB Output is correct
7 Correct 715 ms 135388 KB Output is correct
8 Correct 656 ms 159856 KB Output is correct
9 Correct 728 ms 135188 KB Output is correct
10 Correct 50 ms 86528 KB Output is correct
11 Correct 614 ms 135916 KB Output is correct
12 Correct 662 ms 165868 KB Output is correct
13 Correct 634 ms 138044 KB Output is correct
14 Correct 637 ms 139108 KB Output is correct
15 Correct 645 ms 142948 KB Output is correct
16 Correct 729 ms 138196 KB Output is correct
17 Correct 667 ms 154092 KB Output is correct
18 Correct 753 ms 137940 KB Output is correct
19 Correct 50 ms 86508 KB Output is correct
20 Incorrect 650 ms 139148 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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