oj.uz

Submission #430985

# Submission time Handle Problem Language Result Execution time Memory
430985 2021-06-17T08:43:44 Z juggernaut Regions (IOI09_regions) C++17
65 / 100
 8000 ms 30212 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{
            for(auto to:color[y]){
                ans+=(int)color[x].size();
                ans-=(lower_bound(color[x].begin(),color[x].end(),make_pair(to.sc,0))-color[x].begin())-(lower_bound(color[x].begin(),color[x].end(),make_pair(to.fr,0))-color[x].begin());
                ans-=(int)color[x].size()-(lower_bound(color[x].begin(),color[x].end(),make_pair(to.sc,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 4 ms 6088 KB Output is correct
2 Correct 4 ms 6088 KB Output is correct
3 Correct 6 ms 6088 KB Output is correct
4 Correct 9 ms 6088 KB Output is correct
5 Correct 9 ms 6216 KB Output is correct
6 Correct 22 ms 6216 KB Output is correct
7 Correct 32 ms 6216 KB Output is correct
8 Correct 33 ms 6216 KB Output is correct
9 Correct 50 ms 6728 KB Output is correct
10 Correct 91 ms 6728 KB Output is correct
11 Correct 130 ms 7112 KB Output is correct
12 Correct 151 ms 7648 KB Output is correct
13 Correct 177 ms 7368 KB Output is correct
14 Correct 236 ms 8008 KB Output is correct
15 Correct 285 ms 11120 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8026 ms 11480 KB Time limit exceeded
2 Execution timed out 8018 ms 10200 KB Time limit exceeded
3 Execution timed out 8016 ms 13628 KB Time limit exceeded
4 Correct 300 ms 8024 KB Output is correct
5 Correct 374 ms 9928 KB Output is correct
6 Correct 1381 ms 9392 KB Output is correct
7 Correct 1762 ms 10532 KB Output is correct
8 Correct 1344 ms 16520 KB Output is correct
9 Correct 2305 ms 16816 KB Output is correct
10 Correct 4269 ms 22668 KB Output is correct
11 Correct 3876 ms 16472 KB Output is correct
12 Correct 6099 ms 17744 KB Output is correct
13 Correct 7290 ms 18108 KB Output is correct
14 Execution timed out 8031 ms 18084 KB Time limit exceeded
15 Execution timed out 8048 ms 23120 KB Time limit exceeded
16 Execution timed out 8061 ms 30212 KB Time limit exceeded
17 Execution timed out 8077 ms 28748 KB Time limit exceeded