Submission #878814

#	Time	Username	Problem	Language	Result	Execution time	Memory
878814		niter	Unique Cities (JOI19_ho_t5)	C++14	4 / 100	148 ms	10844 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
#define pb push_back
#define ins isnert
#define pii pair<int,int>
#define ff first
#define ss second
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define ops(x) cerr << x;
#define spac cerr << ' ';
#define entr cerr << endl;
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
#define BAE(x) (x).begin(), (x).end()
#define bye exit(0);
using namespace std;
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int mxn = (int)(1e5) + 10;
vector<int> E[mxn];
int col[mxn];

vector<int> vec_col[mxn];
void dfs(int v, int par, int dis){
    vec_col[dis].pb(col[v]);
    for(auto &u:E[v]){
        if(u == par) continue;
        dfs(u, v, dis + 1);
    }
}
void test_dfs(int v, int par){
    for(auto &u:E[v]){
        if(u == par) continue;
        test_dfs(u, v);
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    loop(i,0,n-1){
        int a, b;
        cin >> a >> b;
        E[a].pb(b);
        E[b].pb(a);
    }
    vector<int> srt_col;
    loop(i,1,n+1){
        cin >> col[i];
        srt_col.pb(col[i]);
    }
    sort(BAE(srt_col));
    srt_col.resize(unique(BAE(srt_col)) - srt_col.begin());
    loop(i,1,n+1){
        col[i] = lower_bound(BAE(srt_col), col[i]) - srt_col.begin() + 1;
    }
    if(n > 2000){
        loop(i,1,n+1){
            test_dfs(i, -1);
        }
        return 0;
    }
    loop(i,1,n+1){
        loop(i,1,n+1) vec_col[i].clear();
        vector<int> vec_ans;
        dfs(i, -1, 0);
        loop(i,1,n+1){
            if(vec_col[i].size() == 1){
                vec_ans.pb(vec_col[i][0]);
            }
        }
        sort(BAE(vec_ans));
        vec_ans.resize(unique(BAE(vec_ans)) - vec_ans.begin());
        cout << vec_ans.size() << '\n';
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32