oj.uz

Submission #877207

# Submission time Handle Problem Language Result Execution time Memory
877207 2023-11-23T03:43:33 Z Kutan Rigged Roads (NOI19_riggedroads) C++14
100 / 100
 319 ms 69456 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);
    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 5 ms 27228 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 8 ms 27480 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27228 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 8 ms 27480 KB Output is correct
4 Correct 5 ms 27224 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27228 KB Output is correct
7 Correct 6 ms 27228 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 38344 KB Output is correct
2 Correct 122 ms 41484 KB Output is correct
3 Correct 81 ms 32988 KB Output is correct
4 Correct 160 ms 55244 KB Output is correct
5 Correct 166 ms 56512 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 46984 KB Output is correct
2 Correct 43 ms 35668 KB Output is correct
3 Correct 27 ms 32592 KB Output is correct
4 Correct 60 ms 42156 KB Output is correct
5 Correct 30 ms 32696 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 62400 KB Output is correct
2 Correct 263 ms 68848 KB Output is correct
3 Correct 58 ms 40532 KB Output is correct
4 Correct 79 ms 45756 KB Output is correct
5 Correct 257 ms 69456 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 54412 KB Output is correct
2 Correct 93 ms 45908 KB Output is correct
3 Correct 261 ms 63832 KB Output is correct
4 Correct 246 ms 61108 KB Output is correct
5 Correct 19 ms 29788 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27228 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 8 ms 27480 KB Output is correct
4 Correct 5 ms 27224 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27228 KB Output is correct
7 Correct 6 ms 27228 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 52 ms 38344 KB Output is correct
10 Correct 122 ms 41484 KB Output is correct
11 Correct 81 ms 32988 KB Output is correct
12 Correct 160 ms 55244 KB Output is correct
13 Correct 166 ms 56512 KB Output is correct
14 Correct 85 ms 46984 KB Output is correct
15 Correct 43 ms 35668 KB Output is correct
16 Correct 27 ms 32592 KB Output is correct
17 Correct 60 ms 42156 KB Output is correct
18 Correct 30 ms 32696 KB Output is correct
19 Correct 193 ms 62400 KB Output is correct
20 Correct 263 ms 68848 KB Output is correct
21 Correct 58 ms 40532 KB Output is correct
22 Correct 79 ms 45756 KB Output is correct
23 Correct 257 ms 69456 KB Output is correct
24 Correct 186 ms 54412 KB Output is correct
25 Correct 93 ms 45908 KB Output is correct
26 Correct 261 ms 63832 KB Output is correct
27 Correct 246 ms 61108 KB Output is correct
28 Correct 19 ms 29788 KB Output is correct
29 Correct 319 ms 59500 KB Output is correct
30 Correct 289 ms 59200 KB Output is correct
31 Correct 275 ms 56460 KB Output is correct
32 Correct 71 ms 33440 KB Output is correct
33 Correct 289 ms 57832 KB Output is correct