oj.uz

Submission #558307

# Submission time Handle Problem Language Result Execution time Memory
558307 2022-05-07T05:48:01 Z Yazan_Alattar Izlet (COI19_izlet) C++14
18 / 100
 505 ms 53520 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];
vector < pair <int,int> > ans;
int n, a[M][M], sz[M][2], p[M][2], col[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;
    }

    return 0;
}

Compilation message

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

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 487 ms 53512 KB Output is correct
3 Correct 474 ms 53520 KB Output is correct
4 Correct 505 ms 53368 KB Output is correct
5 Correct 504 ms 53328 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 487 ms 53512 KB Output is correct
3 Correct 474 ms 53520 KB Output is correct
4 Correct 505 ms 53368 KB Output is correct
5 Correct 504 ms 53328 KB Output is correct
6 Incorrect 1 ms 340 KB Unexpected end of file - int32 expected
7 Halted 0 ms 0 KB -