oj.uz

Submission #428103

# Submission time Handle Problem Language Result Execution time Memory
428103 2021-06-15T08:06:33 Z 장태환(#7562) Counterspells (CPSPC17_counterspells) C++17
0 / 100
 133 ms 44192 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int>link[2][200100];
int s[2][200100];
int e[2][200100];
int c;
vector<pair<pair<int,int>,pair<int,int>>>q;
int pr[200100];
int ans[200100];
int fwtree[200100];
int N;
void upd(int n,int k)
{
    while(n<=N)
    {
        fwtree[n]+=k;
        n+=n&(-n);
    }
}
int get(int n)
{
    int ans=0;
    while(n)
    {
        ans+=fwtree[n];
        n-=n&(-n);
    }
    return ans;
}
void dfs(int ind,int n)
{
    s[ind][n]=++c;
    int i;
    for(i=0;i<link[ind][n].size();i++)
    {
        dfs(ind,link[ind][n][i]);
    }
    e[ind][n]=c;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    int i;
    for(i=1;i<N;i++)
    {
        int a;
        cin >> a;
        link[0][a].push_back(i+1);
    }
    for(i=1;i<N;i++)
    {
        int a;
        cin >> a;
        link[1][a].push_back(i+1);
    }
    dfs(0,1);
    c=0;
    dfs(1,1);
    for(i=1;i<=N;i++)
    {
        pr[s[0][i]]=s[1][i];
    }
    for(i=1;i<=N;i++)
    {
        q.push_back({{e[0][i],i},{s[1][i]-1,e[1][i]}});
        q.push_back({{s[0][i]-1,-i},{s[1][i]-1,e[1][i]}});
    }
    sort(q.begin(),q.end());
    int j=0;
    for(i=1;i<=N;i++)
    {
        while(j<q.size()&&q[j].first.first<i)
        {
            int nod=abs(q[j].first.second);
            int re=q[j].first.second/nod;
            ans[nod]+=re*(-get(q[j].second.first)+get(q[j].second.second));
            j++;
        }
        upd(pr[i],1);
    }
    while(j<q.size()&&q[j].first.first<i)
    {
        int nod=abs(q[j].first.second);
        int re=q[j].first.second/nod;
        ans[nod]+=re*(-get(q[j].second.first)+get(q[j].second.second));
        j++;
    }
    for(i=1;i<=N;i++)
        cout << ans[i]-1<<'\n';
}

Compilation message

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:34:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(i=0;i<link[ind][n].size();i++)
      |             ~^~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         while(j<q.size()&&q[j].first.first<i)
      |               ~^~~~~~~~~
Main.cpp:83:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     while(j<q.size()&&q[j].first.first<i)
      |           ~^~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 19744 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 19744 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 19744 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 133 ms 44192 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 19744 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -