oj.uz

Submission #431082

# Submission time Handle Problem Language Result Execution time Memory
431082 2021-06-17T09:21:42 Z juggernaut Regions (IOI09_regions) C++17
95 / 100
 8000 ms 128356 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(),5000);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 5 ms 6216 KB Output is correct
3 Correct 10 ms 6216 KB Output is correct
4 Correct 6 ms 6344 KB Output is correct
5 Correct 12 ms 6404 KB Output is correct
6 Correct 26 ms 7496 KB Output is correct
7 Correct 32 ms 6984 KB Output is correct
8 Correct 34 ms 7240 KB Output is correct
9 Correct 54 ms 8308 KB Output is correct
10 Correct 95 ms 9120 KB Output is correct
11 Correct 110 ms 8488 KB Output is correct
12 Correct 137 ms 10372 KB Output is correct
13 Correct 156 ms 9184 KB Output is correct
14 Correct 162 ms 8916 KB Output is correct
15 Correct 141 ms 12380 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 724 ms 12460 KB Output is correct
2 Correct 849 ms 11328 KB Output is correct
3 Correct 1126 ms 14948 KB Output is correct
4 Correct 2092 ms 86468 KB Output is correct
5 Correct 3247 ms 108008 KB Output is correct
6 Correct 3760 ms 107464 KB Output is correct
7 Correct 3768 ms 108836 KB Output is correct
8 Correct 4802 ms 114628 KB Output is correct
9 Correct 6015 ms 115048 KB Output is correct
10 Correct 5984 ms 120972 KB Output is correct
11 Correct 7252 ms 114584 KB Output is correct
12 Correct 6790 ms 115868 KB Output is correct
13 Correct 6769 ms 116260 KB Output is correct
14 Correct 5726 ms 116276 KB Output is correct
15 Correct 6937 ms 121484 KB Output is correct
16 Correct 6609 ms 128356 KB Output is correct
17 Execution timed out 8023 ms 126996 KB Time limit exceeded