oj.uz

Submission #430960

# Submission time Handle Problem Language Result Execution time Memory
430960 2021-06-17T08:23:12 Z juggernaut Regions (IOI09_regions) C++17
65 / 100
 8000 ms 28092 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 4 ms 5624 KB Output is correct
2 Correct 4 ms 5576 KB Output is correct
3 Correct 6 ms 5576 KB Output is correct
4 Correct 10 ms 5576 KB Output is correct
5 Correct 11 ms 5576 KB Output is correct
6 Correct 25 ms 5576 KB Output is correct
7 Correct 23 ms 5592 KB Output is correct
8 Correct 33 ms 5760 KB Output is correct
9 Correct 59 ms 6268 KB Output is correct
10 Correct 99 ms 6136 KB Output is correct
11 Correct 136 ms 6344 KB Output is correct
12 Correct 147 ms 6956 KB Output is correct
13 Correct 208 ms 6596 KB Output is correct
14 Correct 303 ms 7172 KB Output is correct
15 Correct 334 ms 10372 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8073 ms 10452 KB Time limit exceeded
2 Execution timed out 8084 ms 9092 KB Time limit exceeded
3 Execution timed out 8074 ms 12500 KB Time limit exceeded
4 Correct 314 ms 7252 KB Output is correct
5 Correct 352 ms 9144 KB Output is correct
6 Correct 1402 ms 8428 KB Output is correct
7 Correct 1760 ms 9412 KB Output is correct
8 Correct 1305 ms 15280 KB Output is correct
9 Correct 2454 ms 14988 KB Output is correct
10 Correct 4305 ms 20508 KB Output is correct
11 Correct 4271 ms 14324 KB Output is correct
12 Correct 5642 ms 16024 KB Output is correct
13 Correct 6299 ms 16468 KB Output is correct
14 Execution timed out 8053 ms 15956 KB Time limit exceeded
15 Execution timed out 8090 ms 20992 KB Time limit exceeded
16 Execution timed out 8013 ms 28092 KB Time limit exceeded
17 Execution timed out 8052 ms 26828 KB Time limit exceeded