Submission #1090760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090760		dpsaveslives	Island (NOI18_island)	C++17	100 / 100	71 ms	17936 KiB

island

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e5+10;
const int MN = 2e5+5;
vector<int> adj[MAXN];
int diff[MAXN],tree[MAXN];
void upd(int p, int x){
    while(p <= MN){
        tree[p] += x;
        p += p&(-p);
        //cout << p << "\n";
    }
}
int query(int p){
    int ret = 0;
    while(p > 0){
        ret += tree[p];
        p -= p&(-p);
    }
    return ret;
}
void dfs(int u, int p){
    for(auto v : adj[u]){
        if(v != p){
            dfs(v,u);
        }
    }
    int num = adj[u].size()-1;
    //cout << u << " " << num << "\n";
    if(num >= 2){
        upd(2,1);
        upd(num+1,-1);
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N,M; cin >> N >> M; //1 to N are leaves
    for(int i = 1;i<=N+M-1;++i){
        int u,v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    dfs(N+1,0);
    for(int i = 2;i<=MN;++i){
        int q = query(i);
        if(q != 0){
            cout << i << " " << q << "\n";
        }
    }
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31
• Subtask 4: 42 / 42