Submission #1149649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149649		FIFI_cpp	Rigged Roads (NOI19_riggedroads)	C++20	30 / 100	789 ms	327680 KiB

riggedroads

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <fstream>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cctype>
#include <string>
#include <cassert>
#include <set>
#include <bitset>
#include <unordered_set>
#include <numeric>

#define all(a) a.begin(), a.end()
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define ppi pair<int,pair<int,int>>
//#define int int64_t

using namespace std;
//    /\_/\
//   (= ._.)
//   / >  \>
// encouraging cat
const int INF = 10000000000000000;
//const int mod = 1000000007;
const int mod = 998244353;
const int MAXN = 200005;
//ifstream fin('xor.in');
//ofstream fout('xor.out');
int n, m;
vector<vector<int>> adj;
vector<vector<pair<int,int>>> mn;
vector<pair<int,int>> lst;
vector<set<int>> store;
vector<bool> inmain;
vector<int> val;
vector<int> valcnt;
void dfs(int v, int p, int edge)
{
    multiset<int> ms;
    for (pair<int,int> u : mn[v]) {
        if (u.first != p)
        {
            dfs(u.first, v, u.second);
            ms.insert(all(store[u.first]));
        }
    }
    ms.insert(all(store[v]));
    store[v].clear();
    vector<int> vc;
    for (auto it: ms)
    {
        vc.pb(it);
    }
    for (int i = 0;i < vc.size();i++)
    {
        if (i < vc.size() - 1 && vc[i] == vc[i + 1])
        {
            i++;
        }
        else
        {
            store[v].insert(vc[i]);
        }
    }
    if (v == 0)
    {
        return;
    }
    if (store[v].size() >= 1)
        val[edge] = *store[v].begin();
    else
        val[edge] = -1;
}
void preprocess(int root) {
    store.resize(n);
    inmain.resize(m);
    val.resize(m);
    lst.resize(m);
    adj.resize(n);
    valcnt.resize(n);
    mn.resize(m);
}
signed main()
{
    cin >> n >> m;
    preprocess(0);
    for (int i = 0;i < m;i++)
    {
        int u,v;
        cin >> u >> v;
        u--;
        v--;
        lst[i] = {u,v};
    }
    for (int i = 0;i < n - 1;i++)
    {
        int x;
        cin >> x;
        x--;
        mn[lst[x].first].pb({lst[x].second, x});
        mn[lst[x].second].pb({lst[x].first, x});
        inmain[x]=true;
    }
    for (int i = 0;i < m;i++)
    {
        if (!inmain[i])
        {
            store[lst[i].first].insert(i);
            store[lst[i].second].insert(i);
        }
    }
    dfs(0,0,-1);
    for (int i = 0;i < m;i++)
    {
        if (val[i] != -1 && inmain[i])
            valcnt[val[i]]++;
    }
    int x = 1;
    vector<int> res(m,-1);
    vector<int> taken(m + 1, -1);
    for (int i = 0;i < m;i++)
    {
        if (inmain[i])
        {
            if (val[i] == -1)
            {
                res[i] = x;
                x++;
                continue;
            }
            if (taken[val[i]] != -1)
            {
                res[i] = taken[val[i]];
                taken[val[i]]++;
            }
            else
            {
                valcnt[val[i]]--;
                res[i] = x;
                x++;
            }
        }
        else
        {
            res[i] = x + valcnt[i];
            taken[i] = x;
            x += valcnt[i];
            x++;
        }
    }
    for (int i = 0;i < m;i++)
    {
        cout << res[i] << " ";
    }
    cout << '\n';
    return 0;
}

Compilation message (stderr)

riggedroads.cpp:36:17: warning: overflow in conversion from 'long int' to 'int' changes value from '10000000000000000' to '1874919424' [-Woverflow]
   36 | const int INF = 10000000000000000;
      |                 ^~~~~~~~~~~~~~~~~

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