oj.uz

답안 #430995

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
430995 2021-06-17T08:46:56 Z juggernaut Regions (IOI09_regions) C++17
65 / 100
 8000 ms 30076 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];
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]>50){
        big[i]=true;
        id[i]=++tot;
    }
    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]){
            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 if(big[x]&&big[y]){
            ans=precalc[id[x]][id[y]];
        }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.sc)-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:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6088 KB Output is correct
2 Correct 5 ms 6088 KB Output is correct
3 Correct 6 ms 6088 KB Output is correct
4 Correct 8 ms 6088 KB Output is correct
5 Correct 11 ms 6216 KB Output is correct
6 Correct 20 ms 6216 KB Output is correct
7 Correct 32 ms 6216 KB Output is correct
8 Correct 35 ms 6216 KB Output is correct
9 Correct 53 ms 6728 KB Output is correct
10 Correct 82 ms 6728 KB Output is correct
11 Correct 127 ms 7112 KB Output is correct
12 Correct 137 ms 7624 KB Output is correct
13 Correct 168 ms 7368 KB Output is correct
14 Correct 235 ms 7904 KB Output is correct
15 Correct 277 ms 11200 KB Output is correct

Subtask #2
50.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8084 ms 11480 KB Time limit exceeded
2 Execution timed out 8026 ms 10048 KB Time limit exceeded
3 Execution timed out 8061 ms 13592 KB Time limit exceeded
4 Correct 304 ms 7932 KB Output is correct
5 Correct 397 ms 9928 KB Output is correct
6 Correct 1432 ms 9416 KB Output is correct
7 Correct 1778 ms 10632 KB Output is correct
8 Correct 1340 ms 16568 KB Output is correct
9 Correct 2378 ms 16852 KB Output is correct
10 Correct 4256 ms 22620 KB Output is correct
11 Correct 4109 ms 16444 KB Output is correct
12 Correct 6331 ms 17728 KB Output is correct
13 Correct 7386 ms 18140 KB Output is correct
14 Execution timed out 8039 ms 17932 KB Time limit exceeded
15 Execution timed out 8071 ms 23104 KB Time limit exceeded
16 Execution timed out 8035 ms 30076 KB Time limit exceeded
17 Execution timed out 8013 ms 28744 KB Time limit exceeded