oj.uz

Submission #430996

# Submission time Handle Problem Language Result Execution time Memory
430996 2021-06-17T08:47:25 Z juggernaut Regions (IOI09_regions) C++17
65 / 100
 8000 ms 30108 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[505][505];
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<=500;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];
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);
    }
    for(int i=1;i<=r;i++)if(cnt[i]>50){
        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]){
            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 if(big[x]&&big[y]){
            ans=precalc[id[x]][id[y]];
        }else{
            assert(!big[y]);
            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.sc)-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:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d%d%d",&n,&r,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d",&reg[1]);
      |     ~~~~~^~~~~~~~~~~~~~
regions.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%d%d",&par,&reg[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6088 KB Output is correct
2 Correct 5 ms 6144 KB Output is correct
3 Correct 5 ms 6088 KB Output is correct
4 Correct 9 ms 6088 KB Output is correct
5 Correct 14 ms 6216 KB Output is correct
6 Correct 25 ms 6284 KB Output is correct
7 Correct 34 ms 6216 KB Output is correct
8 Correct 34 ms 6216 KB Output is correct
9 Correct 55 ms 6732 KB Output is correct
10 Correct 86 ms 6728 KB Output is correct
11 Correct 137 ms 7112 KB Output is correct
12 Correct 137 ms 7624 KB Output is correct
13 Correct 181 ms 7356 KB Output is correct
14 Correct 280 ms 7928 KB Output is correct
15 Correct 295 ms 11256 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8089 ms 11464 KB Time limit exceeded
2 Execution timed out 8055 ms 10020 KB Time limit exceeded
3 Execution timed out 8055 ms 13672 KB Time limit exceeded
4 Correct 246 ms 8028 KB Output is correct
5 Correct 293 ms 9968 KB Output is correct
6 Correct 1407 ms 9416 KB Output is correct
7 Correct 1546 ms 10604 KB Output is correct
8 Correct 1253 ms 16600 KB Output is correct
9 Correct 2203 ms 16864 KB Output is correct
10 Correct 3733 ms 22592 KB Output is correct
11 Correct 3782 ms 16376 KB Output is correct
12 Correct 6035 ms 17652 KB Output is correct
13 Correct 7134 ms 18224 KB Output is correct
14 Execution timed out 8021 ms 18024 KB Time limit exceeded
15 Execution timed out 8054 ms 23120 KB Time limit exceeded
16 Execution timed out 8007 ms 30108 KB Time limit exceeded
17 Execution timed out 8022 ms 28768 KB Time limit exceeded