oj.uz

Submission #270681

# Submission time Handle Problem Language Result Execution time Memory
270681 2020-08-17T22:52:30 Z fivefourthreeone Izlet (COI19_izlet) C++17
100 / 100
 816 ms 36124 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>*/
 
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 62;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = acos(-1);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 3001;
int dsu[mxN];
int find(int a) {
    return dsu[a]==a ? a : dsu[a] = find(dsu[a]);
}
bool merge(int a, int b) {
    a = find(a); b = find(b);
    if(a==b)return false;
    dsu[b] = a;
    return true;
}
int arr[mxN][mxN];
int n;
int cnt;
vector<ttgl> ans;
vector<int> adj[mxN];
int col[mxN];
void dfs(int id, int st, int u, int p) {
    if(arr[id][u]==arr[st][u]) {
        //cout<<id<<" "<<u<<" hi\n";
        merge(id, u);
        return;
    }
    for(int v: adj[u]) {
        if(v^p) {
            dfs(id, st, v, u);
        }
    }
}
int ari_orz;
int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>ari_orz;
    cin>>n;
    owo(i, 0, n) {
        owo(j, 0, n) { 
            cin>>arr[i][j];
        }
    }
    owo(i, 0, n) {
        dsu[i] = i;
    }
    //merge all same color
    owo(i, 0, n) {
        owo(j, 0, n) {
            if(i==j)continue;
            if(arr[i][j]==1&&merge(i, j)) {
                ans.senpai({i, j});
                adj[i].senpai(j);
                adj[j].senpai(i);
            }
        }
    }
    owo(i, 0, n) {
        owo(j, 0, n) {
            if(i==j)continue;
            if(arr[i][j]==2&&merge(i, j)) {
                ans.senpai({i, j});
                adj[i].senpai(j);
                adj[j].senpai(i);
            }
        }
    }
    owo(i, 0, n) {
        dsu[i] = i;
    }
    owo(i, 0, n) {
        for(int k: adj[i]) {
            dfs(i, k, k, i);
        }
    }
    owo(i, 0, n) {
        cout<<(find(i)+1)<<" ";
    }
    cout<<"\n";
    for(auto p: ans) {
        cout<<(p.first+1)<<" "<<(p.second+1)<<"\n";
    }
    
    return 0;
}

Compilation message

izlet.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
izlet.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 738 ms 35960 KB Output is correct
3 Correct 727 ms 35964 KB Output is correct
4 Correct 671 ms 35832 KB Output is correct
5 Correct 696 ms 35900 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 35776 KB Output is correct
2 Correct 668 ms 35892 KB Output is correct
3 Correct 778 ms 36124 KB Output is correct
4 Correct 816 ms 36104 KB Output is correct
5 Correct 644 ms 35832 KB Output is correct
6 Correct 657 ms 35832 KB Output is correct
7 Correct 476 ms 30380 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 738 ms 35960 KB Output is correct
3 Correct 727 ms 35964 KB Output is correct
4 Correct 671 ms 35832 KB Output is correct
5 Correct 696 ms 35900 KB Output is correct
6 Correct 629 ms 35776 KB Output is correct
7 Correct 668 ms 35892 KB Output is correct
8 Correct 778 ms 36124 KB Output is correct
9 Correct 816 ms 36104 KB Output is correct
10 Correct 644 ms 35832 KB Output is correct
11 Correct 657 ms 35832 KB Output is correct
12 Correct 476 ms 30380 KB Output is correct
13 Correct 728 ms 35960 KB Output is correct
14 Correct 809 ms 35832 KB Output is correct
15 Correct 646 ms 35832 KB Output is correct
16 Correct 677 ms 35960 KB Output is correct
17 Correct 676 ms 35828 KB Output is correct
18 Correct 657 ms 35960 KB Output is correct
19 Correct 806 ms 35832 KB Output is correct
20 Correct 698 ms 35960 KB Output is correct
21 Correct 706 ms 35704 KB Output is correct
22 Correct 675 ms 35704 KB Output is correct
23 Correct 707 ms 35704 KB Output is correct
24 Correct 667 ms 35832 KB Output is correct
25 Correct 645 ms 35832 KB Output is correct