oj.uz

Submission #44627

# Submission time Handle Problem Language Result Execution time Memory
44627 2018-04-04T02:06:00 Z imaxblue Construction of Highway (JOI18_construction) C++17
0 / 100
 6 ms 3176 KB 
#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.ub(mp(pos[N], (1<<30)));
    if (i!=L->s.begin()){
        if (i!=L->s.end()){
            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 if (i!=L->s.end()){
        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());
    fox(l, n){
        c[com[l].y]=l+1;
    }
    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){
        get(a[l], b[l]);
    }
    return 0;
}

Compilation message

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:109:9:
     fox(l, res.size()){
         ~~~~~~~~~~~~~             
construction.cpp:109: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:114:9:
     fox(l, res.size()){
         ~~~~~~~~~~~~~             
construction.cpp:114: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:123:9:
     fox(l, v[N].size()){
         ~~~~~~~~~~~~~~            
construction.cpp:123: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:131:9:
     fox(l, v[N].size()){
         ~~~~~~~~~~~~~~            
construction.cpp:131: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:134:9:
     fox(l, v[N].size()){
         ~~~~~~~~~~~~~~            
construction.cpp:134:5: note: in expansion of macro 'fox'
     fox(l, v[N].size()){
     ^~~
construction.cpp: In function 'int main()':
construction.cpp:145:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i", &n);
     ~~~~~^~~~~~~~~~
construction.cpp:147: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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2928 KB Output is correct
3 Correct 4 ms 2928 KB Output is correct
4 Correct 5 ms 2928 KB Output is correct
5 Correct 5 ms 2928 KB Output is correct
6 Correct 4 ms 3100 KB Output is correct
7 Correct 4 ms 3100 KB Output is correct
8 Correct 4 ms 3176 KB Output is correct
9 Correct 4 ms 3176 KB Output is correct
10 Correct 4 ms 3176 KB Output is correct
11 Correct 5 ms 3176 KB Output is correct
12 Correct 5 ms 3176 KB Output is correct
13 Correct 4 ms 3176 KB Output is correct
14 Correct 4 ms 3176 KB Output is correct
15 Correct 4 ms 3176 KB Output is correct
16 Correct 5 ms 3176 KB Output is correct
17 Correct 5 ms 3176 KB Output is correct
18 Correct 6 ms 3176 KB Output is correct
19 Correct 4 ms 3176 KB Output is correct
20 Correct 5 ms 3176 KB Output is correct
21 Correct 5 ms 3176 KB Output is correct
22 Incorrect 4 ms 3176 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2928 KB Output is correct
3 Correct 4 ms 2928 KB Output is correct
4 Correct 5 ms 2928 KB Output is correct
5 Correct 5 ms 2928 KB Output is correct
6 Correct 4 ms 3100 KB Output is correct
7 Correct 4 ms 3100 KB Output is correct
8 Correct 4 ms 3176 KB Output is correct
9 Correct 4 ms 3176 KB Output is correct
10 Correct 4 ms 3176 KB Output is correct
11 Correct 5 ms 3176 KB Output is correct
12 Correct 5 ms 3176 KB Output is correct
13 Correct 4 ms 3176 KB Output is correct
14 Correct 4 ms 3176 KB Output is correct
15 Correct 4 ms 3176 KB Output is correct
16 Correct 5 ms 3176 KB Output is correct
17 Correct 5 ms 3176 KB Output is correct
18 Correct 6 ms 3176 KB Output is correct
19 Correct 4 ms 3176 KB Output is correct
20 Correct 5 ms 3176 KB Output is correct
21 Correct 5 ms 3176 KB Output is correct
22 Incorrect 4 ms 3176 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2928 KB Output is correct
3 Correct 4 ms 2928 KB Output is correct
4 Correct 5 ms 2928 KB Output is correct
5 Correct 5 ms 2928 KB Output is correct
6 Correct 4 ms 3100 KB Output is correct
7 Correct 4 ms 3100 KB Output is correct
8 Correct 4 ms 3176 KB Output is correct
9 Correct 4 ms 3176 KB Output is correct
10 Correct 4 ms 3176 KB Output is correct
11 Correct 5 ms 3176 KB Output is correct
12 Correct 5 ms 3176 KB Output is correct
13 Correct 4 ms 3176 KB Output is correct
14 Correct 4 ms 3176 KB Output is correct
15 Correct 4 ms 3176 KB Output is correct
16 Correct 5 ms 3176 KB Output is correct
17 Correct 5 ms 3176 KB Output is correct
18 Correct 6 ms 3176 KB Output is correct
19 Correct 4 ms 3176 KB Output is correct
20 Correct 5 ms 3176 KB Output is correct
21 Correct 5 ms 3176 KB Output is correct
22 Incorrect 4 ms 3176 KB Output isn't correct
23 Halted 0 ms 0 KB -