답안 #44627 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44627	2018-04-04T02:06:00 Z	imaxblue	Construction of Highway (JOI18_construction)	C++17	0 / 100	6 ms	3176 KB

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.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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #44627

Compilation message

Subtask #1 0 / 7.0

Subtask #2 0 / 9.0

Subtask #3 0 / 84.0

Subtask #1
0 / 7.0

Subtask #2
0 / 9.0

Subtask #3
0 / 84.0