Submission #1259039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259039		phtung	Rigged Roads (NOI19_riggedroads)	C++20	58 / 100	2094 ms	152088 KiB

riggedroads

#include <bits/stdc++.h>

using namespace std;

#define name "IO"
#define int long long 

const int inf = 1e18 + 7; 
const int maxn = 3e5 + 5; 
int n, e; 
vector<pair<int,int>> adj[maxn]; 
vector<int> ans(maxn, 0); 
int cur_val = 1; 

int par[maxn], h[maxn], sz[maxn], num[maxn]; 
int head[maxn], ind[maxn], pos[maxn], arr[maxn]; 
int cnt, curr; 

void dfs(int u, int pre = -1)
{
    sz[u] = 1; 
    for(auto [v, id] : adj[u])
    {
        if(v == pre) continue;
        par[v] = u;
        h[v] = h[u] + 1; 
        num[v] = id; 
        dfs(v, u);
        sz[u] +=  sz[v]; 
    }
}

void hld(int u, int pre = -1)
{
    if(!head[curr])
    {
        head[curr] = u; 
    }

    ind[u] = curr;
    pos[u] = cnt; 
    arr[cnt] = u; 
    cnt++;

    int nxt = 0;

    for(auto [v, id] : adj[u])
    {
        if(v != pre)
        {
            if(!nxt || sz[v] > sz[nxt]) nxt = v; 
        }
    }

    if(nxt) hld(nxt, u); 

    for(auto [v, id] : adj[u])
    {
        if(v != nxt && v != pre)
        {
            curr++; 
            hld(v, u); 
        }
    }
}

vector<int> st[4 * maxn];

vector<int> combine(vector<int> x, vector<int> y)
{
    if(x.size() > y.size())
    {
        for(auto val : y) x.push_back(val);
        return x; 
    }
    else 
    {
        for(auto val : x) y.push_back(val);
        return y; 
    }
}

void build(int id, int l, int r)
{
    if(l == r)
    {
        st[id].push_back(num[arr[l]]); 
        return; 
    }
    int m = l + r >> 1; 
    build(id * 2, l, m);
    build(id * 2 + 1, m + 1, r);
    st[id] = combine(st[id * 2], st[id * 2 + 1]); 
}

vector<int> get(int id, int l, int r, int u, int v)
{
    vector<int>nothing;
    if(l > v || r < u) return nothing; 
    if(l >= u && r <= v) return st[id]; 
    int m = l + r >> 1;
    auto x = get(id * 2, l, m, u, v);
    auto y = get(id * 2 + 1, m + 1, r, u, v); 
    return combine(x, y); 
}

void query(int u, int v, int id)
{
    vector<int> s;
    while(ind[u] != ind[v])
    {
        if(ind[u] > ind[v])
        {
            s = combine(s, get(1, 1, n, pos[head[ind[u]]], pos[u])); 
            u = par[head[ind[u]]]; 
        }
        else 
        {
            s = combine(s, get(1, 1, n, pos[head[ind[v]]], pos[v])); 
            v = par[head[ind[v]]]; 
        }
    }

    if(h[u] < h[v]) s = combine(s, get(1, 1, n, pos[u] + 1, pos[v])); 

    else s = combine(s, get(1, 1, n, pos[v] + 1, pos[u])); 

    sort(s.begin(), s.end()); 

    for(auto x : s)
    {
        if(!ans[x])
        {
            ans[x] = cur_val; 
            cur_val++; 
        }
    }

    ans[id] = cur_val;
    cur_val++; 
    
}

void solve()
{
    cin >> n >> e;

    vector<pair<int,int>> edge(e + 1); 
    for(int i = 1; i <= e; i++)
    {
        int u, v; 
        cin >> u >> v; 
        edge[i] = {u, v}; 
    }

    vector<int> in(e + 1, 0); 

    for(int i = 1; i < n; i++)
    {
        int id;
        cin >> id; 
        in[id] = 1; 
        auto [u, v] = edge[id]; 
        adj[u].push_back({v, id});
        adj[v].push_back({u, id}); 
    }

    curr = cnt = 1; 
    dfs(1); 
    hld(1); 
    build(1, 1, n); 

    for(int i = 1; i <= e; i++)
    {
        if(in[i])
        {
            if(!ans[i]) 
            {
                ans[i] = cur_val; 
                cur_val++; 
            }
        }
        else 
        {
            auto [u, v] = edge[i];
            query(u, v, i); 
        }
    }

    for(int i = 1; i <= e; i++) cout << ans[i] <<  " "; 


}

signed main()
{
    if (fopen (name".INP", "r"))
    {
        freopen (name".INP", "r", stdin);
        freopen (name".OUT", "w", stdout);
    }

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    clock_t start = clock(); 

    int t = 1;

    while(t--) solve(); 

    std::cerr << "Time: " << clock() - start << "ms\n";

    return 0; 

}

Compilation message (stderr)

riggedroads.cpp: In function 'int main()':
riggedroads.cpp:199:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |         freopen (name".INP", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:200:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 |         freopen (name".OUT", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 0 / 32