제출 #471534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
471534		NicolaAbusaad2014	경주 (Race) (IOI11_race)	C++14	0 / 100	15 ms	31692 KiB

race

/**
 * Prof.Nicola
**/
#include "race.h"
#include <bits/stdc++.h>

using namespace std;
#define endl "\n"
#define mp make_pair
#define F first
#define S second
#define REP(i,l,r) for(long long i=(l);i<(r);i++)
#define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--)
const long dx[4]={1,0,-1,0},dz[4]={0,1,0,-1};
const long double pi=3.14159265359;
const long long mod=1e9+7;
long long p(long long x){while(x&(x-1)){x=x&(x-1);}return x;}
long long squared(long long x){return (x*x)%mod;}
long long power(long long x,long long p){if(p==0){return 1;}if(p%2==1){return (power(x,p-1)*x)%mod;}return squared(power(x,p/2));}
long long inv(long long x){return power(x,mod-2);}
template<class T>void re(T&x){cin>>x;}
template<class T1,class T2> void re(pair<T1,T2>&x){re(x.first);re(x.second);}
template<class T>void re(vector<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void re(deque<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void out(T x){cout<<x<<" ";}
template<class T1,class T2>void out(pair<T1,T2>x){out(x.first);out(x.second);cout<<endl;}
template<class T>void out(vector<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>void out(deque<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>void out(set<T>x){while(!x.empty()){out(*x.begin());x.erase(*x.begin());}cout<<endl;}
template<class T1,class T2>void out(map<T1,T2>x){while(!x.empty()){out(*x.begin());x.erase(x.begin()->first);}cout<<endl;}
template<class T>void out(queue<T>x){while(!x.empty()){out(x.front());x.pop();}cout<<endl;}
template<class T>void out(priority_queue<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;}
template<class T>void out(stack<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;}
template<class T>T cross(complex<T>x,complex<T>z){return (conj(x)*z).imag();}
template<class T>T dot(complex<T>x,complex<T>z){return (conj(x)*z).real();}
set<long long>::iterator T;
long long vLE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<=x){l+=z;}z/=2;}return l;}
long long vL(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<x){l+=z;}z/=2;}return l;}
long long vGE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return l;}l=vL(x,VT,l,r);if(l==r){return -1;}return l+1;}
long long vG(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return l;}l=vLE(x,VT,l,r);if(l==r){return -1;}return l+1;}
long long sLE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.begin()>x){return -1;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;}
long long sL(long long x,set<long long>&ST){if(*ST.begin()>=x){return -1;}if(ST.count(x)){T=ST.find(x);T--;return *T;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;}
long long sGE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.rbegin()<x){return -1;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;}
long long sG(long long x,set<long long>&ST){if(*ST.rbegin()<=x){return -1;}if(ST.count(x)){T=ST.find(x);T++;return *T;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;}
struct segment_tree
{
    vector<long long>tree;
    long long operation(long long x,long long z)
    {
        return x+z;
    }
    void build(vector<long long>v)
    {
        tree.clear();
        long long x=v.size();
        while(x&(x-1)){
            x=x&(x-1);
        }
        if(v.size()!=x){
            x*=2;
        }
        tree.resize(x*2);
        tree[0]=x;
        for(long i=0;i<v.size();i++){
            tree[i+x]=v[i];
        }
        for(long i=x-1;i>0;i--){
            tree[i]=operation(tree[i*2],tree[(i*2)+1]);
        }
    }
    long long get(long long l,long long r)
    {
        l+=tree[0];
        r+=tree[0];
        long long ans=0;
        while(l<=r){
            if(l%2==1){
                ans=operation(ans,tree[l]);
            }
            if(r%2==0){
                ans=operation(ans,tree[r]);
            }
            l++;
            l/=2;
            r--;
            r/=2;
        }
        return ans;
    }
    void update(long long x,long long z)
    {
        x+=tree[0];
        tree[x]=z;
        x/=2;
        while(x>0){
            tree[x]=operation(tree[x*2],tree[(x*2)+1]);
            x/=2;
        }
    }
};
long k,ans=1e9;
vector<long>len;
vector<pair<pair<long,long>,pair<long,long> > >mn(1e6+1);
struct tree
{
    long long n,counter;
    vector<vector<pair<long,long> > >edges;
    vector<vector<long> >parent;
    vector<pair<long,long> >sub;
    vector<long>depth,sz,val,rep,to,subtree,path;
    vector<bool>vis;
    segment_tree HLD;
    void scan0(long x,long p,long long l)
    {
        len[x]=l;
        depth[x]=depth[p]+1;
        parent[x][0]=p;
        sz[x]=1;
        counter++;
        sub[x].first=counter;
        REP(i,0,edges[x].size()){
            if(edges[x][i].F==p||vis[edges[x][i].F]){
                continue;
            }
            scan0(edges[x][i].F,x,l+edges[x][i].S);
            sz[x]+=sz[edges[x][i].F];
        }
        sub[x].second=counter;
    }
    void scan(long x,long p,long long l,long h)
    {
        len[x]=l;
        depth[x]=depth[p]+1;
        if(l<=k){
        if(depth[x]<mn[l].F.F){
            if(mn[l].F.S==h){
                mn[l].F.F=depth[x];
            }
            else{
                mn[l].S=mn[l].F;
                mn[l].F=mp(depth[x],h);
            }
        }
        else if(depth[x]<mn[l].F.S){
            if(mn[l].F.S!=h){
                mn[l].S=mp(depth[x],h);
            }
        }
        }
        parent[x][0]=p;
        sz[x]=1;
        counter++;
        sub[x].first=counter;
        REP(i,0,edges[x].size()){
            if(edges[x][i].F==p||vis[edges[x][i].F]){
                continue;
            }
            scan(edges[x][i].F,x,l+edges[x][i].S,h);
            sz[x]+=sz[edges[x][i].F];
        }
        sub[x].second=counter;
    }
    void scan2(long x,long p,long long l,long h)
    {
        if(l>k){
            return;
        }
        if(h==mn[k-l].F.S&&mn[k-l].S.S!=0){
            ans=min(ans,depth[x]+mn[k-l].S.F);
        }
        else if(h!=mn[k-l].F.S){
            ans=min(ans,depth[l]+mn[k-l].F.F);
        }
        sub[x].first=counter;
        REP(i,0,edges[x].size()){
            if(edges[x][i].F==p||vis[edges[x][i].F]){
                continue;
            }
            scan2(edges[x][i].F,x,l+edges[x][i].S,h);
            sz[x]+=sz[edges[x][i].F];
        }
        sub[x].second=counter;
    }
    void scan3(long x,long p,long long l,long h)
    {
        mn[l]=mp(mp(0,0),mp(0,0));
        sub[x].first=counter;
        REP(i,0,edges[x].size()){
            if(edges[x][i].F==p||vis[edges[x][i].F]){
                continue;
            }
            scan3(edges[x][i].F,x,l+edges[x][i].S,h);
            sz[x]+=sz[edges[x][i].F];
        }
        sub[x].second=counter;
    }
    long long operation(long long x,long long z)
    {
        return max(x,z);
    }
    void up(long x,long z)
    {
        bool ok=false;
        to[x]=z;
        REP(i,0,edges[x].size()){
            if(edges[x][i].F==parent[x][0]){
                continue;
            }
            if(sz[edges[x][i].F]>=(sz[x]+1)/2){
                up(edges[x][i].F,z);
                ok=true;
                continue;
            }
            up(edges[x][i].F,edges[x][i].F);
        }
        if(!ok){
            long node=x;
            while(depth[node]>=depth[to[x]]){
                rep[node]=counter;
                counter++;
                node=parent[node][0];
            }
        }
    }
    long long decompose(long x,long z)
    {
        if(rep[to[x]]-rep[x]>=z){
            return HLD.get(rep[x],rep[x]+z);
        }
        return operation(HLD.get(rep[x],rep[to[x]]),decompose(parent[to[x]][0],z-1-(rep[to[x]]-rep[x])));
    }
    long centroid(long x,long p,long z)
    {
        long mx=0,node=x;
        REP(i,0,edges[x].size()){
            if(!vis[edges[x][i].F]&&edges[x][i].F!=p&&sz[edges[x][i].F]>mx){
                mx=sz[edges[x][i].F];
                node=edges[x][i].F;
            }
        }
        if(mx<z){
            return x;
        }
        return centroid(node,x,z);
    }
    void read(long nodes,vector<vector<pair<long,long> > >e)
    {
        n=nodes;
        edges=e;
        val.clear();
        val.resize(n+1);
    }
    void build(long long root=1)
    {
        counter=-1;
        vis.clear();
        vis.resize(n+1);
        depth.clear();
        depth.resize(n+1);
        depth[0]=-1;
        sz.clear();
        sz.resize(n+1);
        rep.clear();
        rep.resize(n+1);
        to.clear();
        to.resize(n+1);
        sub.clear();
        sub.resize(n+1);
        parent.clear();
        parent.resize(n+1);
        REP(i,0,n+1){
            parent[i].resize(21);
        }
        scan(root,0,0,1);
        subtree.clear();
        subtree.resize(n);
        REP(i,1,n+1){
            subtree[sub[i].first]=val[i];
        }
        REP(i,1,21){
            REP(j,1,n+1){
                parent[j][i]=parent[parent[j][i-1]][i-1];
            }
        }
        counter=0;
        up(root,root);
        path.clear();
        path.resize(n);
        REP(i,1,n+1){
            path[rep[i]]=val[i];
        }
    }
    long lift(long x,long z)
    {
        if(z<=0){
            return x;
        }
        pair<long,long long>p;
        p.first=0;
        p.second=1;
        long d=z;
        while(d>1){
            d/=2;
            p.first++;
            p.second*=2;
        }
        while(z>0){
            if(z>=p.second){
                z-=p.second;
                x=parent[x][p.first];
            }
            p.first--;
            p.second/=2;
        }
        return x;
    }
    long LCA(long x,long z)
    {
        long p=0,d=depth[x]-depth[z];
        x=lift(x,d);
        z=lift(z,-d);
        if(x==z){
            return x;
        }
        d=depth[x];
        while(d>1){
            d/=2;
            p++;
        }
        while(p>=0){
            if(parent[x][p]!=parent[z][p]){
                x=parent[x][p];
                z=parent[z][p];
            }
            p--;
        }
        x=parent[x][0];
        return x;
    }
};
tree t;
void solve(long x)
{
    t.scan0(x,0,0);
    x=t.centroid(x,0,(t.sz[x]+1)/2);
    t.vis[x]=true;
    REP(i,0,t.edges[x].size()){
        if(t.vis[t.edges[x][i].F]){
            continue;
        }
        t.scan(t.edges[x][i].F,0,0,t.edges[x][i].F);
    }
    REP(i,0,t.edges[x].size()){
        if(t.vis[t.edges[x][i].F]){
            continue;
        }
        t.scan2(t.edges[x][i].F,0,0,t.edges[x][i].F);
    }
    REP(i,0,t.edges[x].size()){
        if(t.vis[t.edges[x][i].F]){
            continue;
        }
        t.scan3(t.edges[x][i].F,0,0,t.edges[x][i].F);
    }
    REP(i,0,t.edges[x].size()){
        if(t.vis[t.edges[x][i].F]){
            continue;
        }
        solve(t.edges[x][i].F);
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    k=K;
    len.resize(N+1);
    vector<vector<pair<long,long> > >e(N+1);
    REP(i,0,N-1){
        e[H[i][0]].push_back(mp(H[i][1],L[i]));
        e[H[i][1]].push_back(mp(H[i][0],L[i]));
    }
    t.read(N,e);
    t.build();
    return N;
}

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

race.cpp: In member function 'void segment_tree::build(std::vector<long long int>)':
race.cpp:59:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   59 |         if(v.size()!=x){
      |            ~~~~~~~~^~~
race.cpp:64:23: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(long i=0;i<v.size();i++){
      |                      ~^~~~~~~~~
race.cpp: In member function 'void tree::scan0(long int, long int, long long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:121:9: note: in expansion of macro 'REP'
  121 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In member function 'void tree::scan(long int, long int, long long int, long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:154:9: note: in expansion of macro 'REP'
  154 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In member function 'void tree::scan2(long int, long int, long long int, long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:175:9: note: in expansion of macro 'REP'
  175 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In member function 'void tree::scan3(long int, long int, long long int, long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:188:9: note: in expansion of macro 'REP'
  188 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In member function 'void tree::up(long int, long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:205:9: note: in expansion of macro 'REP'
  205 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In member function 'long int tree::centroid(long int, long int, long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:235:9: note: in expansion of macro 'REP'
  235 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In function 'void solve(long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:347:5: note: in expansion of macro 'REP'
  347 |     REP(i,0,t.edges[x].size()){
      |     ^~~
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:353:5: note: in expansion of macro 'REP'
  353 |     REP(i,0,t.edges[x].size()){
      |     ^~~
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:359:5: note: in expansion of macro 'REP'
  359 |     REP(i,0,t.edges[x].size()){
      |     ^~~
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:365:5: note: in expansion of macro 'REP'
  365 |     REP(i,0,t.edges[x].size()){
      |     ^~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57