oj.uz

답안 #558331

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
558331 2022-05-07T06:12:02 Z Yazan_Alattar Izlet (COI19_izlet) C++14
43 / 100
 748 ms 108596 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];
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 = n; i; --i){
            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:98:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   98 |         for(int i = 1; i <= n; ++i) cout << col[i] << " "; cout << endl;
      |         ^~~
izlet.cpp:98:60: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   98 |         for(int i = 1; i <= n; ++i) cout << col[i] << " "; cout << endl;
      |                                                            ^~~~

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 486 ms 36152 KB Output is correct
3 Correct 466 ms 36132 KB Output is correct
4 Correct 501 ms 36052 KB Output is correct
5 Correct 517 ms 36076 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 484 ms 44836 KB Output is correct
2 Correct 486 ms 62420 KB Output is correct
3 Correct 748 ms 100864 KB Output is correct
4 Correct 728 ms 108596 KB Output is correct
5 Correct 451 ms 62468 KB Output is correct
6 Correct 535 ms 69592 KB Output is correct
7 Correct 411 ms 58052 KB Output is correct

Subtask #3
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 486 ms 36152 KB Output is correct
3 Correct 466 ms 36132 KB Output is correct
4 Correct 501 ms 36052 KB Output is correct
5 Correct 517 ms 36076 KB Output is correct
6 Correct 484 ms 44836 KB Output is correct
7 Correct 486 ms 62420 KB Output is correct
8 Correct 748 ms 100864 KB Output is correct
9 Correct 728 ms 108596 KB Output is correct
10 Correct 451 ms 62468 KB Output is correct
11 Correct 535 ms 69592 KB Output is correct
12 Correct 411 ms 58052 KB Output is correct
13 Incorrect 541 ms 74256 KB Output isn't correct
14 Halted 0 ms 0 KB -