oj.uz

Submission #1116278

# Submission time Handle Problem Language Result Execution time Memory
1116278 2024-11-21T12:14:17 Z ro9669 Rigged Roads (NOI19_riggedroads) C++17
9 / 100
 2000 ms 262144 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) int(v.size())
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;

typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;

const int maxN = int(3e5)+7;

int n , m;
vector<int> g[maxN];
ii E[maxN];
bool used[maxN];
int fa[maxN] , nxt[maxN] , p[maxN] , h[maxN] , res[maxN] , cur = 0;

void dfs(int u , int par){
    for (int id : g[u]){
        int v = u ^ (E[id].fi ^ E[id].se);
        if (v != par){
            p[v] = id;
            h[v] = h[u] + 1;
            dfs(v , u);
        }
    }
}

int root(int x){
    if (fa[x] < 0) return x; else return fa[x] = root(fa[x]);
}

void unite(int u , int v){
    u = root(u);
    v = root(v);
    if (u == v) return;
    if (-fa[u] < -fa[v]) swap(u , v);
    fa[u] += fa[v];
    fa[v] = u;
    if (h[nxt[u]] > h[nxt[v]]) nxt[u] = nxt[v];
}

vector<int> pos;

void get(int u , int v){
    pos.clear();
    u = root(u);
    v = root(v);
    while (u != v){
        if (h[nxt[u]] > h[nxt[v]]) swap(u , v);
        int id = p[v];
        if (res[id] == 0) pos.push_back(id);
        int nxt_v = v ^ (E[id].fi ^ E[id].se);
        unite(v , nxt_v);
        v = root(v);
    }
}

void solve(){
    cin >> n >> m;
    for (int i = 1 ; i <= m ; i++){
        int u , v;
        cin >> u >> v;
        E[i] = {u , v};
    }
    for (int i = 1 ; i < n ; i++){
        int x; cin >> x;
        int u = E[x].fi;
        int v = E[x].se;
        used[x] = 1;
        g[u].push_back(x);
        g[v].push_back(x);
    }
    for (int i = 1 ; i <= n ; i++){
        fa[i] = -1;
        nxt[i] = i;
    }
    dfs(1 , 0);
    for (int i = 1 ; i <= m ; i++){
        if (used[i] == 0){
            get(E[i].fi , E[i].se);
            sort(all(pos));
            for (int x : pos) res[x] = ++cur;
            res[i] = ++cur;
        }
        else{
            if (res[i] == 0) res[i] = ++cur;
        }
    }
    for (int i = 1 ; i <= m ; i++) cout << res[i] << " ";
}

#define name "A"

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(name".INP" , "r")){
        freopen(name".INP" , "r" , stdin);
        freopen(name".OUT" , "w" , stdout);
    }
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 11600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 11600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 19904 KB Output is correct
2 Correct 56 ms 23364 KB Output is correct
3 Correct 53 ms 20296 KB Output is correct
4 Correct 89 ms 32184 KB Output is correct
5 Correct 86 ms 33208 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 314 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 361 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 334 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 11600 KB Time limit exceeded
2 Halted 0 ms 0 KB -