oj.uz

Submission #430957

# Submission time Handle Problem Language Result Execution time Memory
430957 2021-06-17T08:21:55 Z juggernaut Regions (IOI09_regions) C++17
65 / 100
 8000 ms 28096 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];
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++)
        color[reg[i]].emplace_back(tin[i],tout[i]);
    for(int i=1;i<=r;i++)sort(color[i].begin(),color[i].end());
    while(q--){
        int x,y;
        scanf("%d%d",&x,&y);
        int ans=0;
        if(big[x]&&big[y]){
            ans=precalc[x][y];
        }else 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());
        }
        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:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d%d%d",&n,&r,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d",&reg[1]);
      |     ~~~~~^~~~~~~~~~~~~~
regions.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%d%d",&par,&reg[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5576 KB Output is correct
2 Correct 5 ms 5576 KB Output is correct
3 Correct 5 ms 5576 KB Output is correct
4 Correct 11 ms 5576 KB Output is correct
5 Correct 12 ms 5576 KB Output is correct
6 Correct 20 ms 5576 KB Output is correct
7 Correct 38 ms 5576 KB Output is correct
8 Correct 22 ms 5760 KB Output is correct
9 Correct 43 ms 6216 KB Output is correct
10 Correct 77 ms 6120 KB Output is correct
11 Correct 129 ms 6344 KB Output is correct
12 Correct 168 ms 6944 KB Output is correct
13 Correct 179 ms 6648 KB Output is correct
14 Correct 227 ms 7212 KB Output is correct
15 Correct 315 ms 10384 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8052 ms 10408 KB Time limit exceeded
2 Execution timed out 8005 ms 9112 KB Time limit exceeded
3 Execution timed out 8031 ms 12496 KB Time limit exceeded
4 Correct 289 ms 7240 KB Output is correct
5 Correct 372 ms 9160 KB Output is correct
6 Correct 1328 ms 8384 KB Output is correct
7 Correct 1621 ms 9404 KB Output is correct
8 Correct 1425 ms 15252 KB Output is correct
9 Correct 2094 ms 14936 KB Output is correct
10 Correct 4261 ms 20640 KB Output is correct
11 Correct 4374 ms 14272 KB Output is correct
12 Correct 5885 ms 16028 KB Output is correct
13 Correct 6983 ms 16480 KB Output is correct
14 Execution timed out 8064 ms 15956 KB Time limit exceeded
15 Execution timed out 8026 ms 20944 KB Time limit exceeded
16 Execution timed out 8064 ms 28096 KB Time limit exceeded
17 Execution timed out 8025 ms 26900 KB Time limit exceeded