oj.uz

Submission #431068

# Submission time Handle Problem Language Result Execution time Memory
431068 2021-06-17T09:14:33 Z juggernaut Regions (IOI09_regions) C++17
100 / 100
 7358 ms 30068 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]>200||r<=500){
        big[i]=true;
        id[i]=++tot;
    }
    if(tot>5000)return -1;
    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: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:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6272 KB Output is correct
2 Correct 4 ms 6216 KB Output is correct
3 Correct 6 ms 6216 KB Output is correct
4 Correct 8 ms 6344 KB Output is correct
5 Correct 11 ms 6344 KB Output is correct
6 Correct 19 ms 7496 KB Output is correct
7 Correct 34 ms 6984 KB Output is correct
8 Correct 43 ms 7296 KB Output is correct
9 Correct 49 ms 8392 KB Output is correct
10 Correct 95 ms 9160 KB Output is correct
11 Correct 106 ms 8472 KB Output is correct
12 Correct 128 ms 10228 KB Output is correct
13 Correct 127 ms 9188 KB Output is correct
14 Correct 162 ms 8860 KB Output is correct
15 Correct 220 ms 12316 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 12448 KB Output is correct
2 Correct 946 ms 11216 KB Output is correct
3 Correct 1321 ms 14916 KB Output is correct
4 Correct 223 ms 8008 KB Output is correct
5 Correct 338 ms 9996 KB Output is correct
6 Correct 1432 ms 9416 KB Output is correct
7 Correct 1426 ms 10568 KB Output is correct
8 Correct 981 ms 16576 KB Output is correct
9 Correct 2132 ms 16756 KB Output is correct
10 Correct 3745 ms 22572 KB Output is correct
11 Correct 4601 ms 16452 KB Output is correct
12 Correct 1616 ms 17632 KB Output is correct
13 Correct 2110 ms 18108 KB Output is correct
14 Correct 2831 ms 18004 KB Output is correct
15 Correct 3474 ms 23092 KB Output is correct
16 Correct 3213 ms 30068 KB Output is correct
17 Correct 7358 ms 28824 KB Output is correct