oj.uz

Submission #705171

# Submission time Handle Problem Language Result Execution time Memory
705171 2023-03-03T13:29:51 Z Nursik Izlet (COI19_izlet) C++14
100 / 100
 648 ms 61400 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <random>

using namespace std;
 
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
 
const ll maxn = 3e3 + 10, maxm = 3e5 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blcok = 400, p2 = 31;
const ld eps = 1e-9;

int s;
int n, c;
int p[maxn], sz[maxn], used[maxn], color[maxn];
int a[maxn][maxn];
vector<int> g[maxn];
int get(int v){
    if (v == p[v])
        return v;
    return p[v] = get(p[v]);
}
void unite(int a, int b){
    int u = a, v = b;
    a = get(a), b = get(b);
    if (a == b)
        return;
    g[u].pb(v);
    g[v].pb(u);
    if (sz[a] > sz[b])
        swap(a, b);
    sz[b] += sz[a];
    p[a] = b;
}
int dfs2(int v, int p, int root, int cur = 1){
    if (p){
        used[color[v]] += 1;
        if (used[color[v]] == 1){
            if (a[root][v] == cur){
                return color[v];
            }
            ++cur;
        }
    }
    for (auto to : g[v]){
        if (color[to] > 0 && to != p){
            int x = dfs2(to, v, root, cur);
            if (x > 0)
                return x;
        }
    }
    used[color[v]] -= 1;
    return 0;
}
void dfs(int v = 1, int p = 0){
    if (p){
        color[v] = dfs2(v, 0, v);
        if (color[v] == 0){
            color[v] = ++c;
        }
        for (int j = 1; j <= n; ++j){
            used[j] = 0;
        }
    }
    for (auto to : g[v]){
        if (to != p){
            dfs(to, v);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    cin >> s;
    cin >> n;
    for (int i = 1; i <= n; ++i){
        p[i] = i, sz[i] = 1;
    }
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j){
            cin >> a[i][j];
            if (a[i][j] == 1){
                unite(i, j);
            }
        }
    }
    vector<int> roots;
    for (int i = 1; i <= n; ++i){
        int x = get(i);
        if (used[x] == 0){
            roots.pb(x);
        }
    }
    for (int i = 0; i < (int)roots.size(); ++i){
        int x = roots[i];
        for (int j = i + 1; j < (int)roots.size(); ++j){
            int y = roots[j];
            if (a[x][y] == 2){
                unite(x, y);
            }
        }
    }
    color[1] = 1;
    c = 1;
    dfs();
    for (int i = 1; i <= n; ++i){
        cout << color[i] << " ";
    }
    cout << '\n';
    for (int i = 1; i <= n; ++i){
        for (auto it : g[i]){
            if (i < it){
                cout << i << " " << it << '\n';
            }
        }
    }
}
/*
*/

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 465 ms 36124 KB Output is correct
3 Correct 429 ms 36208 KB Output is correct
4 Correct 453 ms 36976 KB Output is correct
5 Correct 461 ms 36828 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 36220 KB Output is correct
2 Correct 438 ms 35916 KB Output is correct
3 Correct 592 ms 36288 KB Output is correct
4 Correct 648 ms 36356 KB Output is correct
5 Correct 506 ms 35904 KB Output is correct
6 Correct 462 ms 35848 KB Output is correct
7 Correct 347 ms 30388 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 465 ms 36124 KB Output is correct
3 Correct 429 ms 36208 KB Output is correct
4 Correct 453 ms 36976 KB Output is correct
5 Correct 461 ms 36828 KB Output is correct
6 Correct 401 ms 36220 KB Output is correct
7 Correct 438 ms 35916 KB Output is correct
8 Correct 592 ms 36288 KB Output is correct
9 Correct 648 ms 36356 KB Output is correct
10 Correct 506 ms 35904 KB Output is correct
11 Correct 462 ms 35848 KB Output is correct
12 Correct 347 ms 30388 KB Output is correct
13 Correct 425 ms 35888 KB Output is correct
14 Correct 640 ms 61400 KB Output is correct
15 Correct 563 ms 53476 KB Output is correct
16 Correct 595 ms 57936 KB Output is correct
17 Correct 635 ms 59912 KB Output is correct
18 Correct 502 ms 53436 KB Output is correct
19 Correct 539 ms 53480 KB Output is correct
20 Correct 465 ms 53504 KB Output is correct
21 Correct 496 ms 54168 KB Output is correct
22 Correct 508 ms 53712 KB Output is correct
23 Correct 475 ms 54200 KB Output is correct
24 Correct 495 ms 60580 KB Output is correct
25 Correct 425 ms 53540 KB Output is correct