제출 #1088047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1088047		modwwe	도로 폐쇄 (APIO21_roads)	C++17	100 / 100	347 ms	282108 KiB

roads

#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define int2 long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
 
inline int scan()
{
    char c = getchar_unlocked();
    int x = 0;
    while(c<'0'||c>'9')
    {
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar_unlocked();
    }
    return x;
}
 
void phongbeo();
const int inf=1e9;
const int mod2=1e9+9;
const int  mod1=998244353;
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int2 b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c,d,e;
 
};
 
int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,dem4,l,r,mid,l2,r2,center;
int  i,s10,s12,s11;
int kk;
int el=29;
 
vector<ib> v[100001];
vector<int> v3[100001];
vector<int> v2;
vector<int2> vv;
int depth[100001];
int par[100001];
int a[100001];
int b[100001];
bool cmp(int x,int y)
{
    return depth[x]>depth[y];
}
struct Node
{
    int2 sum;
    int cnt;
  int leaf;
    Node* c[2];
 
    Node()
    {
        sum=cnt=0;
        c[0]=c[1]=NULL;
    }
};
struct Trie
{
 
    Node *root=new Node();
    void add(int x,int y)
    {
        Node* cur=root;
        if(x<0)x=0;
        for(int i=el; i>=0; --i)
        {
            cur->cnt+=y;
            cur->sum+=1ll*x*y;
            int tmp =bit(x,i);
            if(cur->c[tmp]==NULL)
                cur->c[tmp]=new Node();
            cur=cur->c[tmp];
        }
                    cur->sum+=x*y;
        cur->cnt+=y;
        cur->leaf=x;
    }
    ib get(int k)
    {
        Node* cur=root;
        int2 s=0;
        for(int i=el; i>=0; --i)
        {
            if(cur->c[0]==NULL)
            {
                cur=cur->c[1];
            }
            else
            {
                if(cur->c[0]->cnt>=k)cur=cur->c[0];
                else k-=cur->c[0]->cnt,s+=cur->c[0]->sum,cur=cur->c[1];
            }
        }
        s=s+1ll*k*cur->leaf;
        return {cur->leaf,s};
    }
} t[100001];
void dfs(int x,int y)
{
    par[x]=y;
    depth[x]=++dem;
    for(auto f:v[x])
        if(f.a!=y)
        {
            dfs(f.a,x);
            t[x].add(f.b,1);
            a[f.a]=f.b;
            b[f.a]=f.b;
        }
    s8=v[x].size();
    v3[s8-1].pb(x);
}
vector<long long> minimum_closure_costs(int N,vector<int> U,vector<int> V,vector<int> W)
{
    n=N;
    for(int i=1; i<n; i++)
       l=U[i-1],r=V[i-1],s2=W[i-1],l++,r++,v[l].pb({r,s2}),v[r].pb({l,s2}),s5+=s2;
    dfs(1,0);
    vv.pb(s4);
    a[1]=b[1]=1e9+1;
    for(int i=n-2; i>=1; --i)
    {
        s11=v3[i].size();
        for(auto x:v3[i])
            v2.pb(x);
                    if(s11!=0)
        sort(v2.begin(),v2.end(),cmp);
s4=0;
        for(auto x:v2)
        {
           if(x!=1)
        t[par[x]].add(a[x],-1);
   s10=v[x].size();
          ib  ss2=t[x].get(s10-i);
            s4+=ss2.b;
            a[x]=b[x];
            if(ss2.a>0)a[x]-=ss2.a;
            if(a[x]<0)s4+=a[x];
            if(x!=1)
    t[par[x]].add(a[x],1);
        }
        vv.pb(s4);
        s4=0;
    }
    vv.pb(s5);
     reverse(vv.begin(),vv.end());
    return vv;
 
}

컴파일 시 표준 에러 (stderr) 메시지

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:153:53: warning: narrowing conversion of 'r' from 'long long int' to 'int' [-Wnarrowing]
  153 |        l=U[i-1],r=V[i-1],s2=W[i-1],l++,r++,v[l].pb({r,s2}),v[r].pb({l,s2}),s5+=s2;
      |                                                     ^
roads.cpp:153:69: warning: narrowing conversion of 'l' from 'long long int' to 'int' [-Wnarrowing]
  153 |        l=U[i-1],r=V[i-1],s2=W[i-1],l++,r++,v[l].pb({r,s2}),v[r].pb({l,s2}),s5+=s2;
      |                                                                     ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 22 / 22