답안 #299193

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
299193 2020-09-14T14:38:43 Z mat_v Regions (IOI09_regions) C++14
1 / 100
8000 ms 33400 KB
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define pb push_back
#define maxn 200005
#define pair<int,int> pii
#define xx first
#define yy second



using namespace std;
typedef long long ll;

int n,r,q;
int dlt;
int niz[maxn];
bool veci[maxn];
int cale[maxn];
vector<int> graf[maxn];
vector<int> boja[maxn];

int disc[maxn];
int out[maxn];
int gde[maxn];
int slika[505];


int kolko[505][25005][2];


int tajm = 1;
void dfs(int x){
    disc[x] = tajm;
    for(auto c:graf[x]){
        if(c == cale[x])continue;
        tajm++;
        dfs(c);
    }
    out[x] = tajm;
}

void color(int x, int last, int root, int idx){
    kolko[root][niz[x]][idx]++;
    for(auto c:graf[x]){
        if(c == last)continue;
        color(c,x,root,idx);
    }
}

void color2(int x, int root, int idx){
    if(x == 0)return;
    kolko[root][niz[x]][idx]++;
    color2(cale[x], root, idx);
}

bool cmp(int x, int y){
    if(out[x] == out[y])return disc[x] < disc[y];
    return out[x] < out[y];
}

int trg;

int subtr[maxn];
bool mark[maxn];

int val[maxn];


struct kurac{
    int l;
    int op;
    int idx;
    int pre;
};

bool cmpkurac(kurac a, kurac b){
    if(a.l != b.l)return a.l < b.l;
    if(a.l == b.l){
        if(a.op == 0)return 1;
        if(b.op == 0)return 0;
        return a.pre > b.pre;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> n >> r >> q;
    while(dlt * dlt < n)dlt++;
    ff(i,1,n){
        if(i == 1){
            cin >> niz[i];
            boja[niz[i]].pb(i);
            continue;
        }
        cin >> cale[i];
        cin >> niz[i];
        graf[i].pb(cale[i]);
        boja[niz[i]].pb(i);
        graf[cale[i]].pb(i);
    }
    dfs(1);
    int br = 1;
    ff(i,1,r){
        int sta = boja[i].size();
        if(sta >= dlt)veci[i] = 1;
        if(veci[i]){
            slika[br] = i;
            gde[i] = br;
            //cout << i << ": \n";
            for(auto c:boja[i]){
                //cout << c << " ";
                color(c,cale[c],br,0);
                color2(cale[c],br,1);
                kolko[br][i][0]--;
            }
            //cout << kolko[br][1][0] << "\n";
            //cout << "\n";
            br++;
            continue;
        }
        sort(boja[i].begin(), boja[i].end(), cmp);
        vector<kurac> all;
        for(auto c:boja[i]){
            //cout << c << " " << disc[c] << " " << out[c] << "\n";
            all.pb({disc[c], 0, c, 0});
            all.pb({out[c], 1, c, disc[c]});
        }
        sort(all.begin(), all.end(), cmpkurac);
        int sad = 0;
        for(auto c:all){
            if(c.op == 0)sad++;
            else{
                val[c.idx] = sad;
                sad--;
            }
        }
        //return 0;


    }

    while(q--){
        int r1,r2;
        cin >> r1 >> r2;
        if(veci[r1] || veci[r2]){
            //cout << "AAAA\n";
            if(veci[r1]){
                cout << kolko[gde[r1]][r2][0] << endl;
            }
            else{
                cout << kolko[gde[r2]][r1][1] << endl;
            }
        }
        else{
            //cout << "BBBB\n";
            int p1 = 0;
            int p2 = 0;
            int ans = 0;
            while(p1 < boja[r1].size() && p2 < boja[r2].size()){

                int prvi = boja[r1][p1];
                int drugi = boja[r2][p2];
                //cout << prvi << " " << drugi << "\n";
                //cout << disc[prvi] << " " << out[prvi] << " " << out[drugi] << "\n";
                if(out[drugi] > out[prvi]){
                    p1++;
                }
                else{
                    if(out[drugi] <= out[prvi]){
                        if(disc[drugi] > disc[prvi]){
                            ans += val[prvi];
                            p2++;
                        }
                        else{
                            p1++;
                        }
                    }
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}

Compilation message

regions.cpp:5:9: warning: ISO C++11 requires whitespace after the macro name
    5 | #define pair<int,int> pii
      |         ^~~~
regions.cpp: In function 'int main()':
regions.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
regions.cpp:91:5: note: in expansion of macro 'ff'
   91 |     ff(i,1,n){
      |     ^~
regions.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
regions.cpp:105:5: note: in expansion of macro 'ff'
  105 |     ff(i,1,r){
      |     ^~
regions.cpp:161:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |             while(p1 < boja[r1].size() && p2 < boja[r2].size()){
      |                   ~~~^~~~~~~~~~~~~~~~~
regions.cpp:161:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |             while(p1 < boja[r1].size() && p2 < boja[r2].size()){
      |                                           ~~~^~~~~~~~~~~~~~~~~
regions.cpp: In function 'bool cmpkurac(kurac, kurac)':
regions.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
   83 | }
      | ^
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Incorrect 7 ms 9728 KB Output isn't correct
3 Incorrect 9 ms 9728 KB Output isn't correct
4 Incorrect 11 ms 9856 KB Output isn't correct
5 Incorrect 12 ms 9728 KB Output isn't correct
6 Incorrect 16 ms 9856 KB Output isn't correct
7 Incorrect 34 ms 9856 KB Output isn't correct
8 Incorrect 38 ms 9856 KB Output isn't correct
9 Incorrect 57 ms 10240 KB Output isn't correct
10 Incorrect 86 ms 10368 KB Output isn't correct
11 Incorrect 105 ms 10624 KB Output isn't correct
12 Incorrect 130 ms 11008 KB Output isn't correct
13 Incorrect 143 ms 11392 KB Output isn't correct
14 Incorrect 169 ms 11520 KB Output isn't correct
15 Incorrect 269 ms 14584 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8009 ms 15112 KB Time limit exceeded
2 Incorrect 2651 ms 14720 KB Output isn't correct
3 Execution timed out 8089 ms 17064 KB Time limit exceeded
4 Incorrect 250 ms 11640 KB Output isn't correct
5 Incorrect 314 ms 12704 KB Output isn't correct
6 Incorrect 5125 ms 16684 KB Output isn't correct
7 Incorrect 4312 ms 18452 KB Output isn't correct
8 Execution timed out 8013 ms 21696 KB Time limit exceeded
9 Incorrect 1686 ms 19320 KB Output isn't correct
10 Execution timed out 8101 ms 28776 KB Time limit exceeded
11 Incorrect 2404 ms 22064 KB Output isn't correct
12 Execution timed out 8025 ms 21180 KB Time limit exceeded
13 Execution timed out 8042 ms 22008 KB Time limit exceeded
14 Execution timed out 8035 ms 22432 KB Time limit exceeded
15 Execution timed out 8074 ms 26040 KB Time limit exceeded
16 Execution timed out 8029 ms 33400 KB Time limit exceeded
17 Execution timed out 8048 ms 32316 KB Time limit exceeded