oj.uz

답안 #492263

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
492263 2021-12-06T10:15:59 Z lukameladze Regions (IOI09_regions) C++14
95 / 100
 7088 ms 131076 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define int long long
#define pii pair <int, int>
using namespace std;
const int N = 3e5 + 5, B = 450;
int tin,in[N],out[N],anss,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],shes[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 (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;
    }
    for (int j = 0; j < heavy.size(); j++) {
    	shes[heavy[j]] = j;
	}
      dfs(1,0);
      sort(vv.begin(),vv.end());
    for (int i = 0; i < vv.size(); i++) {
        idx[col[vv[i].s]]++;
        ms[col[vv[i].s]].insert({vv[i].f,idx[col[vv[i].s]]});
    }
    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];
                it = ms[r2].lower_bound({in[up],0});
                if (it == ms[r2].end()) continue;
                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<<"\n";
            continue;
        }
        cout<<ans[r1][r2]<<"\n";
    }
}

Compilation message

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

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 42568 KB Output is correct
2 Correct 22 ms 42696 KB Output is correct
3 Correct 22 ms 42568 KB Output is correct
4 Correct 24 ms 42596 KB Output is correct
5 Correct 26 ms 42652 KB Output is correct
6 Correct 35 ms 42720 KB Output is correct
7 Correct 48 ms 42832 KB Output is correct
8 Correct 50 ms 42952 KB Output is correct
9 Correct 65 ms 43864 KB Output is correct
10 Correct 99 ms 44100 KB Output is correct
11 Correct 146 ms 44876 KB Output is correct
12 Correct 155 ms 46024 KB Output is correct
13 Correct 242 ms 46444 KB Output is correct
14 Correct 313 ms 47292 KB Output is correct
15 Correct 429 ms 52404 KB Output is correct

Subtask #2
80.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2362 ms 55648 KB Output is correct
2 Correct 2883 ms 55456 KB Output is correct
3 Correct 3650 ms 59512 KB Output is correct
4 Correct 317 ms 47504 KB Output is correct
5 Correct 393 ms 50680 KB Output is correct
6 Correct 1101 ms 74496 KB Output is correct
7 Correct 2117 ms 63052 KB Output is correct
8 Correct 2965 ms 127204 KB Output is correct
9 Correct 3564 ms 68004 KB Output is correct
10 Runtime error 1291 ms 131076 KB Execution killed with signal 9
11 Correct 7088 ms 75208 KB Output is correct
12 Correct 2290 ms 73872 KB Output is correct
13 Correct 3049 ms 75756 KB Output is correct
14 Correct 3904 ms 98340 KB Output is correct
15 Correct 4922 ms 83276 KB Output is correct
16 Correct 5104 ms 94376 KB Output is correct
17 Correct 5287 ms 114144 KB Output is correct