oj.uz

Submission #829880

# Submission time Handle Problem Language Result Execution time Memory
829880 2023-08-18T15:34:00 Z Pajaraja Two Currencies (JOI23_currencies) C++17
10 / 100
 114 ms 24072 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[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 3 ms 5204 KB Output is correct
2 Correct 3 ms 5332 KB Output is correct
3 Correct 2 ms 5268 KB Output is correct
4 Correct 2 ms 5160 KB Output is correct
5 Correct 12 ms 6100 KB Output is correct
6 Correct 17 ms 6100 KB Output is correct
7 Correct 15 ms 5904 KB Output is correct
8 Correct 17 ms 6188 KB Output is correct
9 Correct 18 ms 6176 KB Output is correct
10 Correct 18 ms 6100 KB Output is correct
11 Correct 19 ms 6100 KB Output is correct
12 Correct 18 ms 6100 KB Output is correct
13 Correct 13 ms 6304 KB Output is correct
14 Correct 14 ms 6304 KB Output is correct
15 Correct 16 ms 6172 KB Output is correct
16 Correct 16 ms 6136 KB Output is correct
17 Correct 17 ms 6156 KB Output is correct
18 Correct 16 ms 6248 KB Output is correct
19 Correct 22 ms 6396 KB Output is correct
20 Correct 16 ms 6176 KB Output is correct
21 Correct 17 ms 6164 KB Output is correct
22 Correct 17 ms 6164 KB Output is correct
23 Correct 16 ms 6228 KB Output is correct
24 Correct 16 ms 6228 KB Output is correct
25 Correct 17 ms 6256 KB Output is correct
26 Correct 14 ms 6100 KB Output is correct
27 Correct 15 ms 6176 KB Output is correct
28 Correct 15 ms 6100 KB Output is correct
29 Correct 16 ms 6256 KB Output is correct
30 Correct 23 ms 6100 KB Output is correct
31 Correct 17 ms 6176 KB Output is correct
32 Correct 17 ms 6172 KB Output is correct
33 Correct 12 ms 6356 KB Output is correct
34 Correct 12 ms 6304 KB Output is correct
35 Correct 12 ms 6356 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5264 KB Output is correct
2 Correct 20 ms 6176 KB Output is correct
3 Correct 17 ms 6168 KB Output is correct
4 Correct 17 ms 6176 KB Output is correct
5 Runtime error 114 ms 24072 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 12 ms 6356 KB Output is correct
3 Correct 12 ms 6356 KB Output is correct
4 Correct 16 ms 6304 KB Output is correct
5 Runtime error 99 ms 22360 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5332 KB Output is correct
3 Correct 2 ms 5268 KB Output is correct
4 Correct 2 ms 5160 KB Output is correct
5 Correct 12 ms 6100 KB Output is correct
6 Correct 17 ms 6100 KB Output is correct
7 Correct 15 ms 5904 KB Output is correct
8 Correct 17 ms 6188 KB Output is correct
9 Correct 18 ms 6176 KB Output is correct
10 Correct 18 ms 6100 KB Output is correct
11 Correct 19 ms 6100 KB Output is correct
12 Correct 18 ms 6100 KB Output is correct
13 Correct 13 ms 6304 KB Output is correct
14 Correct 14 ms 6304 KB Output is correct
15 Correct 16 ms 6172 KB Output is correct
16 Correct 16 ms 6136 KB Output is correct
17 Correct 17 ms 6156 KB Output is correct
18 Correct 16 ms 6248 KB Output is correct
19 Correct 22 ms 6396 KB Output is correct
20 Correct 16 ms 6176 KB Output is correct
21 Correct 17 ms 6164 KB Output is correct
22 Correct 17 ms 6164 KB Output is correct
23 Correct 16 ms 6228 KB Output is correct
24 Correct 16 ms 6228 KB Output is correct
25 Correct 17 ms 6256 KB Output is correct
26 Correct 14 ms 6100 KB Output is correct
27 Correct 15 ms 6176 KB Output is correct
28 Correct 15 ms 6100 KB Output is correct
29 Correct 16 ms 6256 KB Output is correct
30 Correct 23 ms 6100 KB Output is correct
31 Correct 17 ms 6176 KB Output is correct
32 Correct 17 ms 6172 KB Output is correct
33 Correct 12 ms 6356 KB Output is correct
34 Correct 12 ms 6304 KB Output is correct
35 Correct 12 ms 6356 KB Output is correct
36 Correct 2 ms 5264 KB Output is correct
37 Correct 20 ms 6176 KB Output is correct
38 Correct 17 ms 6168 KB Output is correct
39 Correct 17 ms 6176 KB Output is correct
40 Runtime error 114 ms 24072 KB Execution killed with signal 11
41 Halted 0 ms 0 KB -