oj.uz

Submission #829888

# Submission time Handle Problem Language Result Execution time Memory
829888 2023-08-18T15:35:33 Z Pajaraja Two Currencies (JOI23_currencies) C++17
10 / 100
 1266 ms 52872 KB 
#include <bits/stdc++.h>
#define MAXN 100007
#define MAXL 22
using namespace std;
long long bit[2][4*MAXN],y[MAXN],c[MAXN];
int in[2*MAXN],out[2*MAXN],vreme=1,u[MAXN],v[MAXN],p[MAXL][2*MAXN],f[MAXN],t[MAXN],x[MAXN],ans[MAXN],w,z[MAXN],n,m,q;
vector<int> g[2*MAXN],h[MAXN];
pair<int,int> pi[MAXN];
void upd(int k,int ind,long long s)
{
    while(ind<MAXN)
    {
        bit[k][ind]+=s;
        ind+=(ind&-ind);
    }
}
long long parc(int k,int ind)
{
    long long sum=0;
    while(ind)
    {
        sum+=bit[k][ind];
        ind-=(ind&-ind);
    }
    return sum;
}
long long range(int k, int l,int r) {return parc(k,r)-parc(k,l-1);}
void dfs(int s,int f)
{
    p[0][s]=f;
    in[s]=vreme++;
    for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s);
    out[s]=vreme++;
}
bool insub(int a,int b) {return in[a]>=in[b] && out[a]<=out[b];} //jel a u podstablu od b
int lca(int a,int b)
{
    if(insub(a,b)) return b;
    if(insub(b,a)) return a;
    for(int i=MAXL-1;i>=0;i--) if(!insub(a,p[i][b])) b=p[i][b];
    return p[0][b];
}
long long query(int k,int a,int b)
{
    int c=lca(a,b);
    return range(k,in[c],in[a])+range(k,in[c],in[b]);
}
void answerqueries(int l,int r,vector<int> queries)
{
    int s=(l+r)/2;
    while(w<s)
    {
        w++;
        upd(0,in[n+w],c[w]);
        upd(0,out[n+w],-c[w]);
        upd(1,in[n+w],-1);
        upd(1,out[n+w],1);
    }
    while(w>s)
    {
        upd(0,in[n+w],-c[w]);
        upd(0,out[n+w],c[w]);
        upd(1,in[n+w],1);
        upd(1,out[n+w],-1);
        w--;
    }
    vector<int> q1,q2;
    for(int i=0;i<queries.size();i++)
    {
        int ind=queries[i];
        if(query(0,f[ind],t[ind])>y[ind]) q1.push_back(ind);
        else
        {
            q2.push_back(ind);
            ans[ind]=query(1,f[ind],t[ind]);
        }
    }
    if(l==r) return;
    answerqueries(l,s,q1);
    answerqueries(s+1,r,q2);
}
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<n;i++) cin>>u[i]>>v[i];
    for(int i=1;i<=m;i++) cin>>z[i]>>c[i];
    for(int i=1;i<=m;i++) pi[i]={c[i],z[i]};
    sort(pi+1,pi+m+1);
    for(int i=1;i<=m;i++) {c[i]=pi[i].first; z[i]=pi[i].second;}
    for(int i=1;i<n;i++) h[i].push_back(u[i]);
    for(int i=1;i<=m;i++) h[z[i]].push_back(n+i);
    for(int i=1;i<n;i++) h[i].push_back(v[i]);
    for(int i=1;i<n;i++) for(int j=0;j+1<h[i].size();j++)
    {
        g[h[i][j]].push_back(h[i][j+1]);
        g[h[i][j+1]].push_back(h[i][j]);
    }
    dfs(1,1);
    for(int j=1;j<MAXL;j++) for(int i=1;i<=n+m;i++) p[j][i]=p[j-1][p[j-1][i]];
    for(int i=1;i<=q;i++) cin>>f[i]>>t[i]>>x[i]>>y[i];
    for(int i=1;i<=m;i++)
    {
        upd(1,in[n+i],1);
        upd(1,out[n+i],-1);
    }
    vector<int> queries;
    for(int i=1;i<=q;i++) ans[i]=query(1,f[i],t[i]);
    for(int i=1;i<=q;i++) queries.push_back(i);
    answerqueries(1,m,queries);
    for(int i=1;i<=q;i++) cout<<max(x[i]-ans[i],-1)<<endl;
}

Compilation message

currencies.cpp: In function 'void dfs(int, int)':
currencies.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s);
      |                 ~^~~~~~~~~~~~
currencies.cpp: In function 'void answerqueries(int, int, std::vector<int>)':
currencies.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0;i<queries.size();i++)
      |                 ~^~~~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:93:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i=1;i<n;i++) for(int j=0;j+1<h[i].size();j++)
      |                                      ~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 3 ms 7488 KB Output is correct
3 Correct 4 ms 7508 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 13 ms 8388 KB Output is correct
6 Correct 18 ms 8388 KB Output is correct
7 Correct 16 ms 8148 KB Output is correct
8 Correct 18 ms 8404 KB Output is correct
9 Correct 18 ms 8452 KB Output is correct
10 Correct 18 ms 8428 KB Output is correct
11 Correct 19 ms 8424 KB Output is correct
12 Correct 23 ms 8508 KB Output is correct
13 Correct 14 ms 8648 KB Output is correct
14 Correct 15 ms 8528 KB Output is correct
15 Correct 21 ms 8488 KB Output is correct
16 Correct 18 ms 8488 KB Output is correct
17 Correct 18 ms 8400 KB Output is correct
18 Correct 17 ms 8408 KB Output is correct
19 Correct 18 ms 8412 KB Output is correct
20 Correct 18 ms 8412 KB Output is correct
21 Correct 19 ms 8460 KB Output is correct
22 Correct 17 ms 8432 KB Output is correct
23 Correct 17 ms 8528 KB Output is correct
24 Correct 17 ms 8520 KB Output is correct
25 Correct 17 ms 8404 KB Output is correct
26 Correct 16 ms 8464 KB Output is correct
27 Correct 18 ms 8444 KB Output is correct
28 Correct 15 ms 8392 KB Output is correct
29 Correct 20 ms 8520 KB Output is correct
30 Correct 19 ms 8404 KB Output is correct
31 Correct 20 ms 8432 KB Output is correct
32 Correct 18 ms 8404 KB Output is correct
33 Correct 13 ms 8564 KB Output is correct
34 Correct 17 ms 8672 KB Output is correct
35 Correct 16 ms 8660 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 20 ms 8416 KB Output is correct
3 Correct 18 ms 8404 KB Output is correct
4 Correct 18 ms 8416 KB Output is correct
5 Incorrect 1266 ms 48764 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 13 ms 8664 KB Output is correct
3 Correct 16 ms 8660 KB Output is correct
4 Correct 16 ms 8564 KB Output is correct
5 Incorrect 413 ms 52872 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 3 ms 7488 KB Output is correct
3 Correct 4 ms 7508 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 13 ms 8388 KB Output is correct
6 Correct 18 ms 8388 KB Output is correct
7 Correct 16 ms 8148 KB Output is correct
8 Correct 18 ms 8404 KB Output is correct
9 Correct 18 ms 8452 KB Output is correct
10 Correct 18 ms 8428 KB Output is correct
11 Correct 19 ms 8424 KB Output is correct
12 Correct 23 ms 8508 KB Output is correct
13 Correct 14 ms 8648 KB Output is correct
14 Correct 15 ms 8528 KB Output is correct
15 Correct 21 ms 8488 KB Output is correct
16 Correct 18 ms 8488 KB Output is correct
17 Correct 18 ms 8400 KB Output is correct
18 Correct 17 ms 8408 KB Output is correct
19 Correct 18 ms 8412 KB Output is correct
20 Correct 18 ms 8412 KB Output is correct
21 Correct 19 ms 8460 KB Output is correct
22 Correct 17 ms 8432 KB Output is correct
23 Correct 17 ms 8528 KB Output is correct
24 Correct 17 ms 8520 KB Output is correct
25 Correct 17 ms 8404 KB Output is correct
26 Correct 16 ms 8464 KB Output is correct
27 Correct 18 ms 8444 KB Output is correct
28 Correct 15 ms 8392 KB Output is correct
29 Correct 20 ms 8520 KB Output is correct
30 Correct 19 ms 8404 KB Output is correct
31 Correct 20 ms 8432 KB Output is correct
32 Correct 18 ms 8404 KB Output is correct
33 Correct 13 ms 8564 KB Output is correct
34 Correct 17 ms 8672 KB Output is correct
35 Correct 16 ms 8660 KB Output is correct
36 Correct 4 ms 7508 KB Output is correct
37 Correct 20 ms 8416 KB Output is correct
38 Correct 18 ms 8404 KB Output is correct
39 Correct 18 ms 8416 KB Output is correct
40 Incorrect 1266 ms 48764 KB Output isn't correct
41 Halted 0 ms 0 KB -