답안 #299199

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
299199 2020-09-14T14:43:06 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;
        cout << endl;
        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:162:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |             while(p1 < boja[r1].size() && p2 < boja[r2].size()){
      |                   ~~~^~~~~~~~~~~~~~~~~
regions.cpp:162:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |             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 12 ms 9728 KB Output isn't correct
5 Incorrect 16 ms 9728 KB Output isn't correct
6 Incorrect 26 ms 9856 KB Output isn't correct
7 Incorrect 40 ms 9856 KB Output isn't correct
8 Incorrect 40 ms 9984 KB Output isn't correct
9 Incorrect 65 ms 10240 KB Output isn't correct
10 Incorrect 83 ms 10368 KB Output isn't correct
11 Incorrect 116 ms 10624 KB Output isn't correct
12 Incorrect 142 ms 11008 KB Output isn't correct
13 Incorrect 145 ms 11168 KB Output isn't correct
14 Incorrect 145 ms 11520 KB Output isn't correct
15 Incorrect 294 ms 14584 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8054 ms 15228 KB Time limit exceeded
2 Incorrect 3237 ms 14708 KB Output isn't correct
3 Execution timed out 8042 ms 17056 KB Time limit exceeded
4 Incorrect 216 ms 11648 KB Output isn't correct
5 Incorrect 391 ms 12664 KB Output isn't correct
6 Incorrect 5869 ms 16652 KB Output isn't correct
7 Incorrect 3748 ms 18424 KB Output isn't correct
8 Execution timed out 8067 ms 21880 KB Time limit exceeded
9 Incorrect 2232 ms 19448 KB Output isn't correct
10 Execution timed out 8076 ms 28624 KB Time limit exceeded
11 Incorrect 3219 ms 21880 KB Output isn't correct
12 Execution timed out 8074 ms 21168 KB Time limit exceeded
13 Execution timed out 8055 ms 22008 KB Time limit exceeded
14 Execution timed out 8035 ms 22392 KB Time limit exceeded
15 Execution timed out 8045 ms 25980 KB Time limit exceeded
16 Execution timed out 8074 ms 33400 KB Time limit exceeded
17 Execution timed out 8074 ms 32280 KB Time limit exceeded