oj.uz

답안 #431048

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431048 2021-06-17T09:06:10 Z juggernaut Regions (IOI09_regions) C++17
85 / 100
 8000 ms 30172 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]>10){
        big[i]=true;
        id[i]=++tot;
    }
    if(tot>500)return -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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6088 KB Output is correct
2 Correct 4 ms 6124 KB Output is correct
3 Correct 7 ms 6088 KB Output is correct
4 Correct 12 ms 6088 KB Output is correct
5 Correct 11 ms 6216 KB Output is correct
6 Correct 19 ms 6216 KB Output is correct
7 Correct 41 ms 6216 KB Output is correct
8 Correct 37 ms 6216 KB Output is correct
9 Correct 54 ms 6728 KB Output is correct
10 Correct 89 ms 6728 KB Output is correct
11 Correct 125 ms 7112 KB Output is correct
12 Correct 129 ms 7624 KB Output is correct
13 Correct 150 ms 7388 KB Output is correct
14 Correct 275 ms 8008 KB Output is correct
15 Correct 292 ms 11204 KB Output is correct

Subtask #2
70.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8028 ms 11472 KB Time limit exceeded
2 Execution timed out 8047 ms 10012 KB Time limit exceeded
3 Execution timed out 8026 ms 13632 KB Time limit exceeded
4 Correct 239 ms 8000 KB Output is correct
5 Correct 357 ms 9928 KB Output is correct
6 Correct 1478 ms 9424 KB Output is correct
7 Correct 1443 ms 10516 KB Output is correct
8 Correct 1131 ms 16648 KB Output is correct
9 Correct 2013 ms 16832 KB Output is correct
10 Correct 3880 ms 22592 KB Output is correct
11 Correct 4605 ms 16368 KB Output is correct
12 Correct 1677 ms 17648 KB Output is correct
13 Correct 2237 ms 18112 KB Output is correct
14 Correct 2490 ms 18000 KB Output is correct
15 Correct 3367 ms 23104 KB Output is correct
16 Correct 2878 ms 30172 KB Output is correct
17 Correct 7523 ms 28792 KB Output is correct