oj.uz

Submission #431024

# Submission time Handle Problem Language Result Execution time Memory
431024 2021-06-17T08:59:11 Z juggernaut Regions (IOI09_regions) C++17
0 / 100
 141 ms 30052 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]>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]){
            return -1;
            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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 6088 KB Execution failed because the return code was nonzero
2 Runtime error 4 ms 6144 KB Execution failed because the return code was nonzero
3 Runtime error 4 ms 6088 KB Execution failed because the return code was nonzero
4 Runtime error 5 ms 6088 KB Execution failed because the return code was nonzero
5 Runtime error 5 ms 6272 KB Execution failed because the return code was nonzero
6 Runtime error 4 ms 6216 KB Execution failed because the return code was nonzero
7 Runtime error 5 ms 6216 KB Execution failed because the return code was nonzero
8 Runtime error 6 ms 6216 KB Execution failed because the return code was nonzero
9 Runtime error 7 ms 6728 KB Execution failed because the return code was nonzero
10 Runtime error 11 ms 6728 KB Execution failed because the return code was nonzero
11 Runtime error 14 ms 7100 KB Execution failed because the return code was nonzero
12 Runtime error 15 ms 7656 KB Execution failed because the return code was nonzero
13 Runtime error 21 ms 7340 KB Execution failed because the return code was nonzero
14 Runtime error 25 ms 7988 KB Execution failed because the return code was nonzero
15 Runtime error 22 ms 11212 KB Execution failed because the return code was nonzero

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 11484 KB Execution failed because the return code was nonzero
2 Runtime error 49 ms 10004 KB Execution failed because the return code was nonzero
3 Runtime error 52 ms 13608 KB Execution failed because the return code was nonzero
4 Runtime error 22 ms 7984 KB Execution failed because the return code was nonzero
5 Runtime error 24 ms 9944 KB Execution failed because the return code was nonzero
6 Runtime error 32 ms 9420 KB Execution failed because the return code was nonzero
7 Runtime error 53 ms 10568 KB Execution failed because the return code was nonzero
8 Runtime error 56 ms 16556 KB Execution failed because the return code was nonzero
9 Runtime error 95 ms 16976 KB Execution failed because the return code was nonzero
10 Runtime error 100 ms 22624 KB Execution failed because the return code was nonzero
11 Runtime error 130 ms 16440 KB Execution failed because the return code was nonzero
12 Runtime error 139 ms 17696 KB Execution failed because the return code was nonzero
13 Runtime error 121 ms 18160 KB Execution failed because the return code was nonzero
14 Runtime error 141 ms 17984 KB Execution failed because the return code was nonzero
15 Runtime error 130 ms 23172 KB Execution failed because the return code was nonzero
16 Runtime error 126 ms 30052 KB Execution failed because the return code was nonzero
17 Runtime error 113 ms 28808 KB Execution failed because the return code was nonzero