oj.uz

Submission #558416

# Submission time Handle Problem Language Result Execution time Memory
558416 2022-05-07T09:34:16 Z Yazan_Alattar Izlet (COI19_izlet) C++14
18 / 100
 487 ms 44860 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define aint(x) x.begin(), x.end()
const int M = 3007;
const ll inf = 2e9;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-6;
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;

vector <int> adj[M], v[M];
vector < pair <int,int> > ans;
int n, a[M][M], sz[M][2], p[M][2], col[M], cur[M], b[M];
bool vist[M][M];

void dfs(int node, int p){
    for(auto i : adj[node]) if(i != p){
        col[i] = col[node] ^ 1;
        dfs(i, node);
    }
    return;
}

int root(int x, int c){
    while(p[x][c] != x){
        p[x][c] = p[p[x][c]][c];
        x = p[x][c];
    }
    return x;
}

void connect(int x, int y, int c){
    x = root(x, c); y = root(y, c);
    if(x == y) return;
    if(sz[x][c] > sz[y][c]) swap(x, y);

    p[x][c] = y;
    sz[y][c] += sz[x][c];
    return;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int subtask; cin >> subtask;
    if(subtask == 1){
        cin >> n;
        for(int i = 1; i <= n; ++i) for(int j = 0; j < 2; ++j) p[i][j] = i, sz[i][j] = 1;

        for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) cin >> a[i][j];

        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j) if(root(i, 0) != root(j, 0) && a[i][j] == 1){
                ans.pb({i, j});
                connect(i, j, 0);
                connect(i, j, 1);
            }
        }

        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j) if(root(i, 1) != root(j, 1) && a[i][j] == 2){
                adj[root(i, 0)].pb(root(j, 0));
                adj[root(j, 0)].pb(root(i, 0));

                ans.pb({i, j});
                connect(i, j, 1);
            }
        }

        dfs(root(1, 0), 0);

        for(int i = 1; i <= n; ++i) cout << col[root(i, 0)]  + 1 << " "; cout << endl;
        for(auto i : ans) cout << i.F << " " << i.S << endl;
    }
    else{
        int mx = 0;
        cin >> n;
        for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) cin >> a[i][j], mx = max(mx, a[i][j]);

        for(int i = 1; i <= n; ++i) for(int j = i; j <= n; ++j) if(i == j || a[i][j] > a[i][j - 1]) v[j].pb(i);

        for(int i = 1; i <= n; ++i) cur[i] = 1;

        for(int i = 1; i <= n; ++i) b[i] = i;
        random_shuffle(b + 1, b + n + 1);

        for(int xx = 1; xx <= n; ++xx){
            int i = b[xx];
            for(int j = 1; j <= n; ++j) while(vist[j][cur[j]]) ++cur[j];

            int mx = 0;
            for(auto j : v[i]) mx = max(mx, cur[j]);
            for(auto j : v[i]) vist[j][mx] = 1;
            col[i] = mx;
        }

        for(int i = 1; i <= n; ++i) cout << col[i] << " "; cout << endl;
        for(int i = 1; i < n; ++i) cout << i << " " << i + 1 << endl;
    }

    return 0;
}

Compilation message

izlet.cpp: In function 'int main()':
izlet.cpp:78:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   78 |         for(int i = 1; i <= n; ++i) cout << col[root(i, 0)]  + 1 << " "; cout << endl;
      |         ^~~
izlet.cpp:78:74: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   78 |         for(int i = 1; i <= n; ++i) cout << col[root(i, 0)]  + 1 << " "; cout << endl;
      |                                                                          ^~~~
izlet.cpp:103:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  103 |         for(int i = 1; i <= n; ++i) cout << col[i] << " "; cout << endl;
      |         ^~~
izlet.cpp:103:60: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  103 |         for(int i = 1; i <= n; ++i) cout << col[i] << " "; cout << endl;
      |                                                            ^~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 468 ms 36348 KB Output is correct
3 Correct 454 ms 36324 KB Output is correct
4 Correct 487 ms 36448 KB Output is correct
5 Correct 478 ms 36560 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 454 ms 44860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 468 ms 36348 KB Output is correct
3 Correct 454 ms 36324 KB Output is correct
4 Correct 487 ms 36448 KB Output is correct
5 Correct 478 ms 36560 KB Output is correct
6 Incorrect 454 ms 44860 KB Output isn't correct
7 Halted 0 ms 0 KB -