oj.uz

Submission #431036

# Submission time Handle Problem Language Result Execution time Memory
431036 2021-06-17T09:02:14 Z juggernaut Regions (IOI09_regions) C++17
85 / 100
 8000 ms 30144 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]>20){
        big[i]=true;
        id[i]=++tot;
    }
    if(tot>5000)exit(-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 4 ms 6124 KB Output is correct
2 Correct 4 ms 6088 KB Output is correct
3 Correct 7 ms 6088 KB Output is correct
4 Correct 8 ms 6088 KB Output is correct
5 Correct 13 ms 6216 KB Output is correct
6 Correct 25 ms 6216 KB Output is correct
7 Correct 32 ms 6216 KB Output is correct
8 Correct 46 ms 6216 KB Output is correct
9 Correct 55 ms 6728 KB Output is correct
10 Correct 83 ms 6728 KB Output is correct
11 Correct 130 ms 7112 KB Output is correct
12 Correct 128 ms 7624 KB Output is correct
13 Correct 174 ms 7376 KB Output is correct
14 Correct 213 ms 8008 KB Output is correct
15 Correct 227 ms 11188 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8025 ms 11348 KB Time limit exceeded
2 Execution timed out 8003 ms 10112 KB Time limit exceeded
3 Execution timed out 8061 ms 13668 KB Time limit exceeded
4 Correct 223 ms 8008 KB Output is correct
5 Correct 388 ms 10036 KB Output is correct
6 Correct 1311 ms 9408 KB Output is correct
7 Correct 1299 ms 10560 KB Output is correct
8 Correct 1238 ms 16572 KB Output is correct
9 Correct 1883 ms 16788 KB Output is correct
10 Correct 3716 ms 22520 KB Output is correct
11 Correct 4266 ms 16392 KB Output is correct
12 Correct 1389 ms 17728 KB Output is correct
13 Correct 1860 ms 18152 KB Output is correct
14 Correct 2126 ms 18004 KB Output is correct
15 Correct 2868 ms 23104 KB Output is correct
16 Correct 2748 ms 30144 KB Output is correct
17 Correct 7140 ms 28736 KB Output is correct