oj.uz

Submission #431013

# Submission time Handle Problem Language Result Execution time Memory
431013 2021-06-17T08:54:45 Z juggernaut Regions (IOI09_regions) C++17
65 / 100
 8000 ms 30064 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];
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]>5){
        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{
            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: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 4 ms 6144 KB Output is correct
2 Correct 4 ms 6088 KB Output is correct
3 Correct 6 ms 6088 KB Output is correct
4 Correct 6 ms 6272 KB Output is correct
5 Correct 13 ms 6216 KB Output is correct
6 Correct 26 ms 6216 KB Output is correct
7 Correct 31 ms 6284 KB Output is correct
8 Correct 30 ms 6344 KB Output is correct
9 Correct 48 ms 6764 KB Output is correct
10 Correct 86 ms 6784 KB Output is correct
11 Correct 120 ms 7076 KB Output is correct
12 Correct 150 ms 7704 KB Output is correct
13 Correct 185 ms 7340 KB Output is correct
14 Correct 278 ms 7948 KB Output is correct
15 Correct 310 ms 11192 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8093 ms 11472 KB Time limit exceeded
2 Execution timed out 8048 ms 10128 KB Time limit exceeded
3 Execution timed out 8042 ms 13604 KB Time limit exceeded
4 Correct 283 ms 8008 KB Output is correct
5 Correct 407 ms 9928 KB Output is correct
6 Correct 1205 ms 9408 KB Output is correct
7 Correct 1569 ms 10616 KB Output is correct
8 Correct 1354 ms 16492 KB Output is correct
9 Correct 2147 ms 16832 KB Output is correct
10 Correct 4013 ms 22584 KB Output is correct
11 Correct 4144 ms 16440 KB Output is correct
12 Correct 5924 ms 17736 KB Output is correct
13 Correct 7166 ms 18108 KB Output is correct
14 Execution timed out 8058 ms 17896 KB Time limit exceeded
15 Execution timed out 8052 ms 23132 KB Time limit exceeded
16 Execution timed out 8061 ms 30064 KB Time limit exceeded
17 Execution timed out 8039 ms 28732 KB Time limit exceeded