oj.uz

Submission #431086

# Submission time Handle Problem Language Result Execution time Memory
431086 2021-06-17T09:24:21 Z juggernaut Regions (IOI09_regions) C++17
100 / 100
 7379 ms 38216 KB 
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
typedef long long ll;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef IOI2021SG
    #define printl(args...)printf(args)
#else
    #define printl(args...)((void)0)
#endif
int n,r,q;
int reg[200005];
vector<int>g[200005];
int timer;
int tin[200005];
int tout[200005];
int precalc[5005][5005];
bool big[25005];
int id[25005];
int tot;
int cnt[25005];
int tmp[25005];
void dfs(int v){
    if(big[reg[v]])for(int i=1;i<=tot;i++)precalc[i][id[reg[v]]]+=tmp[i];
    tmp[id[reg[v]]]++;
    tin[v]=++timer;
    for(int to:g[v])dfs(to);
    tout[v]=++timer;
    tmp[id[reg[v]]]--;
}
vector<pair<int,int>>color[25005];
vector<int>spec[25005];
bool cvota[25005];
int main(){
    scanf("%d%d%d",&n,&r,&q);
    scanf("%d",&reg[1]);
    cnt[reg[1]]++;
    for(int i=2;i<=n;i++){
        int par;
        cnt[reg[i]]++;
        scanf("%d%d",&par,&reg[i]);
        g[par].push_back(i);
    }
    vector<pair<int,int>>vec;
    for(int i=1;i<=r;i++)vec.emplace_back(cnt[i],i);
    sort(vec.rbegin(),vec.rend());
    for(int i=0;i<min((int)vec.size(),1000);i++)cvota[vec[i].sc]=true;
    for(int i=1;i<=r;i++)if(cvota[i]){
        big[i]=true;
        id[i]=++tot;
    }
    dfs(1);
    for(int i=1;i<=n;i++){
        spec[reg[i]].push_back(tout[i]);
        color[reg[i]].emplace_back(tin[i],tout[i]);
    }
    for(int i=1;i<=r;i++){
        sort(color[i].begin(),color[i].end());
        sort(spec[i].begin(),spec[i].end());
    }
    while(q--){
        int x,y;
        scanf("%d%d",&x,&y);
        int ans=0;
        if(big[x]&&big[y]){
            ans=precalc[id[x]][id[y]];
        }else if(color[x].size()<color[y].size()){
            for(auto to:color[x]){
                ans+=(lower_bound(color[y].begin(),color[y].end(),make_pair(to.sc,0))-color[y].begin())-(lower_bound(color[y].begin(),color[y].end(),make_pair(to.fr,0))-color[y].begin());
            }
        }else{
            for(auto to:color[y]){
                ans+=(lower_bound(color[x].begin(),color[x].end(),make_pair(to.fr,0))-color[x].begin());
                ans-=lower_bound(spec[x].begin(),spec[x].end(),to.fr)-spec[x].begin();
            }
        }
        printf("%d\n",ans);
        fflush(stdout);
    }
}

Compilation message

regions.cpp: In function 'void usaco(std::string)':
regions.cpp:5:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:5:66: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d%d%d",&n,&r,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d",&reg[1]);
      |     ~~~~~^~~~~~~~~~~~~~
regions.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf("%d%d",&par,&reg[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6216 KB Output is correct
2 Correct 4 ms 6216 KB Output is correct
3 Correct 6 ms 6216 KB Output is correct
4 Correct 9 ms 6344 KB Output is correct
5 Correct 11 ms 6344 KB Output is correct
6 Correct 20 ms 7496 KB Output is correct
7 Correct 28 ms 6984 KB Output is correct
8 Correct 32 ms 7308 KB Output is correct
9 Correct 47 ms 8392 KB Output is correct
10 Correct 89 ms 9116 KB Output is correct
11 Correct 110 ms 8392 KB Output is correct
12 Correct 122 ms 10316 KB Output is correct
13 Correct 153 ms 9220 KB Output is correct
14 Correct 163 ms 8984 KB Output is correct
15 Correct 180 ms 12328 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 12464 KB Output is correct
2 Correct 854 ms 11212 KB Output is correct
3 Correct 1397 ms 14912 KB Output is correct
4 Correct 346 ms 15944 KB Output is correct
5 Correct 437 ms 17928 KB Output is correct
6 Correct 1378 ms 17448 KB Output is correct
7 Correct 1551 ms 18680 KB Output is correct
8 Correct 1116 ms 24616 KB Output is correct
9 Correct 2201 ms 24972 KB Output is correct
10 Correct 4041 ms 30824 KB Output is correct
11 Correct 4776 ms 24604 KB Output is correct
12 Correct 2033 ms 25828 KB Output is correct
13 Correct 2673 ms 26248 KB Output is correct
14 Correct 2562 ms 26136 KB Output is correct
15 Correct 3297 ms 31460 KB Output is correct
16 Correct 3202 ms 38216 KB Output is correct
17 Correct 7379 ms 37052 KB Output is correct