Submission #44629

#	Time	Username	Problem	Language	Result	Execution time	Memory
44629		imaxblue	Construction of Highway (JOI18_construction)	C++17	100 / 100	520 ms	25904 KiB

construction

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define vi vector<int>
#define vpii vector<pii>
#define vp3i vector<p3i>
#define vpll vector<pll>
#define vp3l vector<p3l>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() ((rand() << 14)+rand())
#define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0)
char _;
#define pi 3.14159265358979323846

int n, a[100005], b[100005], c[100005];
vector<int> v[100005];
int sub[100005], bit[100005];

void add(int P, int V){
    for(; P<=100002; P+=P&-P){
        bit[P]+=V;
    }
}
int sum(int P, int C=0){
    for(; P>0; P-=P&-P) C+=bit[P];
    return C;
}
struct line{
    set<pii> s;
    int par;
    line(int P){
        par=P;
        s=set<pii>();
    }
};
line*lines[100005];
int pos[100005];
set<pii>::iterator i, j;
void mod(int N, int V){
    if (N==-1) return;
    line* L=lines[N];
    //cout << "*" << pos[N] << ' '<< N << ' ' << V << endl;
    while(1){
        i=L->s.ub(mp(pos[N], (1<<30)));
        if (i==L->s.begin()) break;
        --i;
        L->s.erase(i);
    }
    L->s.insert(mp(pos[N], V));
    mod(L->par, V);
}
int dis=0, sz;
vector<pii> res;
void query(int N){
    if (N==-1) return;
    line* L=lines[N];
    i=L->s.lb(mp(pos[N], 0));
    if (i!=L->s.begin()){
        j=i; --j;
        sz=pos[N]-j->x;
        if (res.size() && res.back().x==i->y) res.back().y+=sz;
        else res.push_back(mp(i->y, sz));
        --i;
        for (; ; --i){
            if (i==L->s.begin()){
                sz=i->x;
            } else {
                j=i; --j;
                sz=i->x-j->x;
            }
            if (res.size() && res.back().x==i->y) res.back().y+=sz;
            else res.push_back(mp(i->y, sz));
            if (i==L->s.begin()) break;
        }
    } else {
        sz=pos[N];
        if (res.size() && res.back().x==i->y) res.back().y+=sz;
        else res.push_back(mp(i->y, sz));
    }
    query(L->par);
}
void get(int A, int B){
    ll ans=0;
    res.clear();
    query(A);
    //cout << A << ' ' << B << endl;
    fox(l, res.size()){
        ans+=1LL*sum(res[l].x-1)*res[l].y;
        add(res[l].x, res[l].y);
        //cout << res[l].x << ':' << res[l].y << ' ';
    }
    fox(l, res.size()){
        add(res[l].x, -res[l].y);
    }
    //cout << endl;
    mod(B, c[B]);
    printf("%lli\n", ans);
}
void dfs0(int N){
    sub[N]=1;
    fox(l, v[N].size()){
        dfs0(v[N][l]);
        sub[N]+=sub[v[N][l]];
    }
}
void dfs(int N, line*L, int P){
    int best=0;
    pos[N]=P; lines[N]=L;
    fox(l, v[N].size()){
        if (sub[v[N][l]]>sub[v[N][best]]) best=l;
    }
    fox(l, v[N].size()){
        if (l!=best){
            line*tmp=new line(N);
            dfs(v[N][l], tmp, 1);
        } else {
            dfs(v[N][l], L, P+1);
        }
    }
}
vector<pii> com;
int main(){
    scanf("%i", &n);
    fox1(l, n){
        scanf("%i", c+l);
        com.pb(mp(c[l], l));
    }
    sort(com.begin(), com.end());
    int p=0;
    fox(l, n){
        if (l==0 || com[l].x!=com[l-1].x) ++p;
        c[com[l].y]=p;
    }
    fox(l, n-1){
        scanf("%i%i", a+l, b+l);
        v[a[l]].pb(b[l]);
    }
    dfs0(1);
    line*tmp=new line(-1);
    dfs(1, tmp, 1);
    mod(1, c[1]);
    fox(l, n-1){
        //cout << a[l] << ' '<< b[l] << ' ' << c[b[l]] << endl;
        get(a[l], b[l]);
        //if (l==20) break;
    }
    return 0;
}
/*
15
1 1 1 2 1 2 2 1 2 2 2 2 1 2 2
1 2
1 3
2 4
4 5
1 6
4 7
2 8
4 9
5 10
9 11
8 12
5 13
10 14
9 15

10
1 1 1 2 1 2 2 1 2 2
1 2
1 3
2 4
4 5
1 6
4 7
2 8
4 9
5 10
*/

Compilation message (stderr)

construction.cpp: In function 'void get(int, int)':
construction.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
construction.cpp:107:9:
     fox(l, res.size()){
         ~~~~~~~~~~~~~             
construction.cpp:107:5: note: in expansion of macro 'fox'
     fox(l, res.size()){
     ^~~
construction.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
construction.cpp:112:9:
     fox(l, res.size()){
         ~~~~~~~~~~~~~             
construction.cpp:112:5: note: in expansion of macro 'fox'
     fox(l, res.size()){
     ^~~
construction.cpp: In function 'void dfs0(int)':
construction.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
construction.cpp:121:9:
     fox(l, v[N].size()){
         ~~~~~~~~~~~~~~            
construction.cpp:121:5: note: in expansion of macro 'fox'
     fox(l, v[N].size()){
     ^~~
construction.cpp: In function 'void dfs(int, line*, int)':
construction.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
construction.cpp:129:9:
     fox(l, v[N].size()){
         ~~~~~~~~~~~~~~            
construction.cpp:129:5: note: in expansion of macro 'fox'
     fox(l, v[N].size()){
     ^~~
construction.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
construction.cpp:132:9:
     fox(l, v[N].size()){
         ~~~~~~~~~~~~~~            
construction.cpp:132:5: note: in expansion of macro 'fox'
     fox(l, v[N].size()){
     ^~~
construction.cpp: In function 'int main()':
construction.cpp:143:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i", &n);
     ~~~~~^~~~~~~~~~
construction.cpp:145:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i", c+l);
         ~~~~~^~~~~~~~~~~
construction.cpp:155:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i", a+l, b+l);
         ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84