oj.uz

Submission #431640

# Submission time Handle Problem Language Result Execution time Memory
431640 2021-06-17T13:57:19 Z juggernaut Regions (IOI09_regions) C++17
100 / 100
 4565 ms 49956 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];
unordered_map<int,int>cash[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(cash[x].count(y))ans=cash[x][y];
        else 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();
            }
        }
      cash[x][y]=ans;
        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:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d%d%d",&n,&r,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%d",&reg[1]);
      |     ~~~~~^~~~~~~~~~~~~~
regions.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d%d",&par,&reg[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7548 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Correct 6 ms 7624 KB Output is correct
4 Correct 10 ms 7736 KB Output is correct
5 Correct 13 ms 7812 KB Output is correct
6 Correct 22 ms 8968 KB Output is correct
7 Correct 34 ms 8448 KB Output is correct
8 Correct 41 ms 8896 KB Output is correct
9 Correct 58 ms 9884 KB Output is correct
10 Correct 84 ms 10780 KB Output is correct
11 Correct 76 ms 10152 KB Output is correct
12 Correct 138 ms 12072 KB Output is correct
13 Correct 152 ms 11048 KB Output is correct
14 Correct 161 ms 10832 KB Output is correct
15 Correct 199 ms 14424 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 815 ms 14900 KB Output is correct
2 Correct 975 ms 13696 KB Output is correct
3 Correct 1103 ms 18832 KB Output is correct
4 Correct 375 ms 18508 KB Output is correct
5 Correct 496 ms 20980 KB Output is correct
6 Correct 767 ms 20512 KB Output is correct
7 Correct 1016 ms 21368 KB Output is correct
8 Correct 1104 ms 29092 KB Output is correct
9 Correct 2229 ms 32304 KB Output is correct
10 Correct 4131 ms 40576 KB Output is correct
11 Correct 4565 ms 35824 KB Output is correct
12 Correct 1703 ms 31996 KB Output is correct
13 Correct 2414 ms 33576 KB Output is correct
14 Correct 2486 ms 34356 KB Output is correct
15 Correct 3742 ms 42060 KB Output is correct
16 Correct 3563 ms 49956 KB Output is correct
17 Correct 3320 ms 47068 KB Output is correct