oj.uz

Submission #877206

# Submission time Handle Problem Language Result Execution time Memory
877206 2023-11-23T03:42:11 Z Kutan Rigged Roads (NOI19_riggedroads) C++14
100 / 100
 329 ms 59612 KB 
// Cao Quang Hung
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long , long long>
#define vi vector<int>
#define vpii vector<pii>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define IN(x,y) ((y).find((x))!=(y).end())
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define FOR(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define dem(x) __builtin_popcount(x)
#define Mask(x) (1LL << (x))
#define BIT(x, i) ((x) >> (i) & 1)
#define ln '\n'
#define io_faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
///mt19937 rnd(time(0));

const int INF = 1e9 , mod = 1e9 + 7;

template <class T1, class T2>
inline T1 mul(T1& x, const T2 &k){ return x = (1LL * x * k) % mod; }

template <class T1 , class T2>
inline T1 pw(T1 x, T2 k){T1 res = 1; for (; k ; k >>= 1){ if (k & 1) mul(res, x); mul(x, x); } return res;}

template <class T>
inline bool minimize(T &x, const T &y){ if (x > y){x = y; return 1;} return 0; }

template <class T>
inline bool maximize(T &x, const T &y){ if (x < y){x = y; return 1;} return 0; }

template <class T>
inline void add(T &x , const T &y){ if ((x += y) >= mod) x -= mod; }

template <class T>
inline T product (const T &x , const T &y) { return 1LL * x * y % mod; }

#define PROB "a"
void file(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp","r",stdin);
        freopen(PROB".out","w",stdout);
    }
}
void sinh_(){
//    srand(time(0));
//    freopen(PROB".inp" , "w" , stdout);
//    int n;
}

typedef long long ll;
typedef double db;
const int N = 3e5 + 5;

int n, m, mst[N];
int depth[N], idx[N], par[N];
int deg[N], ans[N];

int sz[N], mx[N], idHld[N];
int base[N], depthHld[N], head[N];

bool on_mst[N], vis[N];
pii edge[N]; 
vi adj[N], g[N];

int other(int x, int id) {
    return x ^ edge[id].first ^ edge[id].second;
}

void readip(){
    cin >> n >> m;
    REP(i, 1, m) cin >> edge[i].fi >> edge[i].se;
    REP(i, 1, n - 1) {
        cin >> mst[i];
        on_mst[mst[i]] = true;
        int u = edge[mst[i]].first;
        int v = edge[mst[i]].second;
        adj[u].eb(mst[i]);
        adj[v].eb(mst[i]);
    }
}

void dfs_mst(int u, int p) {
    sz[u] = 1;
    mx[u] = -1;
    for (int &id : adj[u]) {
        int v = other(u, id);
        if (v == p) continue;
        
        par[v] = u;

        depth[v] = depth[u] + 1;
        idx[v] = id;
        dfs_mst(v, u);
        sz[u] += sz[v];
        if (mx[u] == -1 || sz[mx[u]] < sz[v])
            mx[u] = v;
    }
}

namespace sub12356{
    bool check() {
        if (n == m) return true;
        if (n <= 1000 && m <= 1000) return true;

        REP(i, 1, n - 1) {
            int u = edge[mst[i]].first;
            int v = edge[mst[i]].second;
            if (u == 1 || v == 1) continue;
            return false;
        }

        return true;
    }

    void prepare() {
        REP(i, 1, m) if (!on_mst[i]) {
            int u = edge[i].first;
            int v = edge[i].second;

            if (depth[u] > depth[v]) swap(u, v);
            while(depth[v] > depth[u]) {
                int ID = idx[v];
                g[i].eb(ID);
                ++deg[i];
                v = par[v];
            }
            while(u != v) {
                int ID = idx[u];
                g[i].eb(ID);
                ++deg[i];

                ID = idx[v];
                g[i].eb(ID);
                ++deg[i];

                u = par[u];
                v = par[v];
            }
        }
    }

    void solve() {  
        prepare();

        int cnt = 0;
        REP(i, 1, m) if (!vis[i]) {
            vector<int> v;
            for (int x : g[i]) if (!vis[x]) v.eb(x);
            sort(ALL(v));

            for (int u : v) {
                vis[u] = true;
                ans[u] = ++cnt;
            }
            vis[i] = true;
            ans[i] = ++cnt;
        }
        REP(i, 1, m) cout << ans[i] << ' ';
    }
};

namespace sub_full {
    set<int> s;
    int timeHld = 0;
    int cnt = 0;

    void hld(int u, int p) {
        idHld[u] = ++timeHld;
        base[timeHld] = u;

        if (mx[u] == -1) return;
        depthHld[mx[u]] = depthHld[u];
        head[mx[u]] = head[u];
        hld(mx[u], u);

        for (int &id : adj[u]) {
            int v = other(u, id);
            if (v == mx[u] || v == p) continue;
            depthHld[v] = depthHld[u] + 1;
            head[v] = v;
            hld(v, u);
        }
    }   

    vector<int> curEdge;
    void path(int u, int v) {
        while(head[u] != head[v]) {
            if (depthHld[u] > depthHld[v]) 
                swap(u, v);

            int l = idHld[head[v]], r = idHld[v];
            if (s.empty()) return;
            auto it = s.lower_bound(l);
            while(it != s.end() && *it <= r) {
                int pos = *it;
                int hihi = idx[base[pos]];  
                if (!vis[hihi]) curEdge.eb(hihi);
                it = s.erase(it);
            }
            v = par[head[v]];
        }

        if (idHld[u] > idHld[v]) swap(u, v);

        int l = idHld[u] + 1;
        int r = idHld[v];
        if (s.empty()) return;
        auto it = s.lower_bound(l);
        while(it != s.end() && *it <= r) {
            int pos = *it;
            int hihi = idx[base[pos]];  
            if (!vis[hihi]) curEdge.eb(hihi);
            it = s.erase(it);
        }
    }

    void solve() {
        head[1] = 1;
        depthHld[1] = 1;
        REP(i, 2, n) s.insert(i);
        hld(1, -1);
        REP(i, 1, m) if (!vis[i]) {
            if (on_mst[i]) {
                vis[i] = true;
                ans[i] = ++cnt;
                continue;
            }

            int u = edge[i].fi, v = edge[i].se;
            curEdge.clear();
            path(u, v);
            sort(ALL(curEdge));
            for (int x : curEdge) {
                vis[x] = true;
                ans[x] = ++cnt;
            }
            vis[i] = true;
            ans[i] = ++cnt;
        }
        REP(i, 1, m) cout << ans[i] << ' ';
    }   
};

void solve(){   
    dfs_mst(1, -1);

    if (sub12356::check()) {
        sub12356::solve();
        return;
    }

    sub_full::solve();
}

int main(){
    sinh_();
    io_faster
    file();
    int t = 1;
//    cin >> t;
    while (t--){
        readip();
        solve();
    }
}

Compilation message

riggedroads.cpp: In function 'void readip()':
riggedroads.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
riggedroads.cpp:156:5: note: in expansion of macro 'REP'
  156 |     REP(i, 1, m) cin >> edge[i].fi >> edge[i].se;
      |     ^~~
riggedroads.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
riggedroads.cpp:157:5: note: in expansion of macro 'REP'
  157 |     REP(i, 1, n - 1) {
      |     ^~~
riggedroads.cpp: In function 'bool sub12356::check()':
riggedroads.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
riggedroads.cpp:190:9: note: in expansion of macro 'REP'
  190 |         REP(i, 1, n - 1) {
      |         ^~~
riggedroads.cpp: In function 'void sub12356::prepare()':
riggedroads.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
riggedroads.cpp:201:9: note: in expansion of macro 'REP'
  201 |         REP(i, 1, m) if (!on_mst[i]) {
      |         ^~~
riggedroads.cpp: In function 'void sub12356::solve()':
riggedroads.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
riggedroads.cpp:231:9: note: in expansion of macro 'REP'
  231 |         REP(i, 1, m) if (!vis[i]) {
      |         ^~~
riggedroads.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
riggedroads.cpp:243:9: note: in expansion of macro 'REP'
  243 |         REP(i, 1, m) cout << ans[i] << ' ';
      |         ^~~
riggedroads.cpp: In function 'void sub_full::solve()':
riggedroads.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
riggedroads.cpp:305:9: note: in expansion of macro 'REP'
  305 |         REP(i, 2, n) s.insert(i);
      |         ^~~
riggedroads.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
riggedroads.cpp:307:9: note: in expansion of macro 'REP'
  307 |         REP(i, 1, m) if (!vis[i]) {
      |         ^~~
riggedroads.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
riggedroads.cpp:325:9: note: in expansion of macro 'REP'
  325 |         REP(i, 1, m) cout << ans[i] << ' ';
      |         ^~~
riggedroads.cpp: In function 'void file()':
riggedroads.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(PROB".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(PROB".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25180 KB Output is correct
2 Correct 4 ms 25180 KB Output is correct
3 Correct 4 ms 25180 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25180 KB Output is correct
2 Correct 4 ms 25180 KB Output is correct
3 Correct 4 ms 25180 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 5 ms 25436 KB Output is correct
6 Correct 5 ms 25692 KB Output is correct
7 Correct 4 ms 25180 KB Output is correct
8 Correct 5 ms 25180 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 31952 KB Output is correct
2 Correct 62 ms 35768 KB Output is correct
3 Correct 72 ms 37844 KB Output is correct
4 Correct 86 ms 40700 KB Output is correct
5 Correct 92 ms 41424 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 47444 KB Output is correct
2 Correct 45 ms 35692 KB Output is correct
3 Correct 24 ms 32660 KB Output is correct
4 Correct 60 ms 42172 KB Output is correct
5 Correct 24 ms 32604 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 50388 KB Output is correct
2 Correct 144 ms 55840 KB Output is correct
3 Correct 37 ms 35336 KB Output is correct
4 Correct 54 ms 39108 KB Output is correct
5 Correct 200 ms 54560 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 45432 KB Output is correct
2 Correct 61 ms 39252 KB Output is correct
3 Correct 214 ms 49272 KB Output is correct
4 Correct 169 ms 47676 KB Output is correct
5 Correct 15 ms 26456 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25180 KB Output is correct
2 Correct 4 ms 25180 KB Output is correct
3 Correct 4 ms 25180 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 5 ms 25436 KB Output is correct
6 Correct 5 ms 25692 KB Output is correct
7 Correct 4 ms 25180 KB Output is correct
8 Correct 5 ms 25180 KB Output is correct
9 Correct 33 ms 31952 KB Output is correct
10 Correct 62 ms 35768 KB Output is correct
11 Correct 72 ms 37844 KB Output is correct
12 Correct 86 ms 40700 KB Output is correct
13 Correct 92 ms 41424 KB Output is correct
14 Correct 82 ms 47444 KB Output is correct
15 Correct 45 ms 35692 KB Output is correct
16 Correct 24 ms 32660 KB Output is correct
17 Correct 60 ms 42172 KB Output is correct
18 Correct 24 ms 32604 KB Output is correct
19 Correct 165 ms 50388 KB Output is correct
20 Correct 144 ms 55840 KB Output is correct
21 Correct 37 ms 35336 KB Output is correct
22 Correct 54 ms 39108 KB Output is correct
23 Correct 200 ms 54560 KB Output is correct
24 Correct 94 ms 45432 KB Output is correct
25 Correct 61 ms 39252 KB Output is correct
26 Correct 214 ms 49272 KB Output is correct
27 Correct 169 ms 47676 KB Output is correct
28 Correct 15 ms 26456 KB Output is correct
29 Correct 254 ms 59612 KB Output is correct
30 Correct 279 ms 59280 KB Output is correct
31 Correct 329 ms 56820 KB Output is correct
32 Correct 64 ms 33364 KB Output is correct
33 Correct 241 ms 57688 KB Output is correct