oj.uz

Submission #430939

# Submission time Handle Problem Language Result Execution time Memory
430939 2021-06-17T08:12:01 Z juggernaut Regions (IOI09_regions) C++17
65 / 100
 8000 ms 22132 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];
void dfs(int v){
    tin[v]=++timer;
    for(int to:g[v])dfs(to);
    tout[v]=++timer;
}
vector<pair<int,int>>color[25005];
int main(){
    scanf("%d%d%d",&n,&r,&q);
    scanf("%d",&reg[1]);
    for(int i=2;i<=n;i++){
        int par;
        scanf("%d%d",&par,&reg[i]);
        g[par].push_back(i);
    }
    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;
        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:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d%d%d",&n,&r,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d",&reg[1]);
      |     ~~~~~^~~~~~~~~~~~~~
regions.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d%d",&par,&reg[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         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 4 ms 5576 KB Output is correct
3 Correct 6 ms 5576 KB Output is correct
4 Correct 9 ms 5576 KB Output is correct
5 Correct 12 ms 5632 KB Output is correct
6 Correct 18 ms 5576 KB Output is correct
7 Correct 30 ms 5576 KB Output is correct
8 Correct 23 ms 5704 KB Output is correct
9 Correct 59 ms 5960 KB Output is correct
10 Correct 94 ms 6088 KB Output is correct
11 Correct 134 ms 6344 KB Output is correct
12 Correct 173 ms 6728 KB Output is correct
13 Correct 174 ms 6600 KB Output is correct
14 Correct 299 ms 7112 KB Output is correct
15 Correct 211 ms 9068 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8054 ms 10012 KB Time limit exceeded
2 Execution timed out 8071 ms 9024 KB Time limit exceeded
3 Execution timed out 8050 ms 11424 KB Time limit exceeded
4 Correct 282 ms 7144 KB Output is correct
5 Correct 378 ms 8384 KB Output is correct
6 Correct 1446 ms 8256 KB Output is correct
7 Correct 1720 ms 9228 KB Output is correct
8 Correct 1070 ms 13056 KB Output is correct
9 Correct 2263 ms 14400 KB Output is correct
10 Correct 4158 ms 17720 KB Output is correct
11 Correct 4136 ms 14128 KB Output is correct
12 Correct 6104 ms 15904 KB Output is correct
13 Correct 7043 ms 15856 KB Output is correct
14 Execution timed out 8073 ms 15604 KB Time limit exceeded
15 Execution timed out 8053 ms 18744 KB Time limit exceeded
16 Execution timed out 8034 ms 22132 KB Time limit exceeded
17 Execution timed out 8029 ms 21632 KB Time limit exceeded