oj.uz

답안 #492115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
492115 2021-12-05T14:06:04 Z lukameladze Regions (IOI09_regions) C++14
95 / 100
 6012 ms 131076 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int N = 2e5 + 5, B = 400;
int tin,in[N],out[N],r1,r2,fer,n,le,ri,up,hea[N],lig[N],col[N],r,q,p[N],idx[N];
multiset <pii> :: iterator it;
int mpp[N];
map <int,int>ans[N];
vector <int> heavy,light;
vector <int> v[N],v1[N];
multiset <pii> ms[N];
vector <pii> vv;
multiset <int> mss;
void dfs(int a, int p) {
    tin++;
    in[a] = tin;
    vv.pb({in[a],a});
    for (int i = 0; i < v[a].size(); i++) {
        int to = v[a][i];
        if (to == p) continue;
        dfs(to,a);
    }
    out[a] = tin;
}
void dfs1(int a, int p) {
    if (hea[col[a]]) {
        mpp[col[a]]++;
    }
    for (int j = 0; j < heavy.size(); j++) {
        fer = heavy[j];
        //if (fer == 1 && col[a] == 3)
        //cout<<fer<<" "<<a<<" "<<col[a]<<endl;
        if (mpp[fer]) ans[fer][col[a]]+= mpp[fer];
    }
    for (int i = 0; i < v[a].size(); i++) {
        int to = v[a][i];
        if (to == p) continue;
        dfs1(to,a);
    }
    if (hea[col[a]]) mpp[col[a]]--;
}
main() {
    cin>>n>>r>>q;
    for (int i = 1; i <= n; i++) {
       if (i != 1) cin>>p[i],v[p[i]].pb(i),v[i].pb(p[i]);
        cin>>col[i];
        v1[col[i]].pb(i);
    }
    for (int i = 1; i <= r; i++) {
        if (v1[i].size() >= B) heavy.pb(i), hea[i] = 1;
        else light.pb(i),lig[i] = 1;
    }
      dfs(1,0);
      sort(vv.begin(),vv.end());
    for (int i = 0; i < vv.size(); i++) {
       // if (!hea[col[vv[i].s]]) continue;
  
        idx[col[vv[i].s]]++;
         //    cout<<vv[i].s<<" "<<vv[i].f<<" "<<col[vv[i].s]<<" "<<idx[col[vv[i].s]]<<endl;
        ms[col[vv[i].s]].insert({vv[i].f,idx[col[vv[i].s]]});
    }
    //ins[feri].insert({ini, meramdenea});
   /* for (int i = 1; i <= r; i++) {
        coll = i;
        for (int j = 0; j < v1[coll].size(); j++) {
            ins[coll].pb(in[v1[coll][j]]);
        }
    }*/
  
    dfs1(1,0);
    while(q--) {
        cin>>r1>>r2;
        if (lig[r1]) {
            int anss = 0;
            for (int i = 0; i < v1[r1].size(); i++) {
                up = v1[r1][i];
              //  cout<<up<<"s"<<endl;
                it = ms[r2].lower_bound({in[up],0});
                if (it == ms[r2].end()) continue;
            //   cout<<r2<<" "<<(*it).s<<endl;
                le = (*it).s;
                it = ms[r2].upper_bound({out[up],1e9});
                if (it == ms[r2].end()) ri = ms[r2].size();
                else ri = (*it).s - 1;
                anss += (ri - le + 1);
            }
            cout<<anss<<endl;
            continue;
        }
        cout<<ans[r1][r2]<<endl;
    }
}

Compilation message

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
regions.cpp: In function 'void dfs1(int, int)':
regions.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int j = 0; j < heavy.size(); j++) {
      |                     ~~^~~~~~~~~~~~~~
regions.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main() {
      | ^~~~
regions.cpp: In function 'int main()':
regions.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i < vv.size(); i++) {
      |                     ~~^~~~~~~~~~~
regions.cpp:78:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for (int i = 0; i < v1[r1].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 28616 KB Output is correct
2 Correct 15 ms 28488 KB Output is correct
3 Correct 15 ms 28488 KB Output is correct
4 Correct 23 ms 28488 KB Output is correct
5 Correct 23 ms 28488 KB Output is correct
6 Correct 31 ms 28596 KB Output is correct
7 Correct 39 ms 28616 KB Output is correct
8 Correct 55 ms 28708 KB Output is correct
9 Correct 69 ms 29512 KB Output is correct
10 Correct 112 ms 29640 KB Output is correct
11 Correct 189 ms 30140 KB Output is correct
12 Correct 212 ms 31028 KB Output is correct
13 Correct 243 ms 31060 KB Output is correct
14 Correct 325 ms 31808 KB Output is correct
15 Correct 417 ms 36552 KB Output is correct

Subtask #2
80.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2475 ms 38044 KB Output is correct
2 Correct 2850 ms 37432 KB Output is correct
3 Correct 4415 ms 41416 KB Output is correct
4 Correct 407 ms 31932 KB Output is correct
5 Correct 504 ms 34848 KB Output is correct
6 Correct 1289 ms 51992 KB Output is correct
7 Correct 2234 ms 49392 KB Output is correct
8 Correct 3216 ms 92780 KB Output is correct
9 Correct 2998 ms 47000 KB Output is correct
10 Runtime error 2463 ms 131076 KB Execution killed with signal 9
11 Correct 6012 ms 51152 KB Output is correct
12 Correct 2048 ms 50864 KB Output is correct
13 Correct 2943 ms 52428 KB Output is correct
14 Correct 3873 ms 68960 KB Output is correct
15 Correct 4108 ms 59568 KB Output is correct
16 Correct 4148 ms 70780 KB Output is correct
17 Correct 4559 ms 84848 KB Output is correct