oj.uz

Submission #270677

# Submission time Handle Problem Language Result Execution time Memory
270677 2020-08-17T22:41:41 Z fivefourthreeone Izlet (COI19_izlet) C++17
100 / 100
 832 ms 61560 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];
int dfs(int id, int st, int u, int p) {
    int node = -1;
    //cout<<id<<" "<<st<<" "<<u<<" "<<arr[id][u]<<" "<<arr[st][u]<<" "<<col[u]<<"\n";
    if(arr[id][u]==arr[st][u]) {
        return u;
    }
    for(int v: adj[u]) {
        if(v^p) {
            node = max(node, dfs(id, st, v, u));
        }
    }
    return node;
}
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]) {
            int same = dfs(i, k, k, i);
            if(same!=-1) {
                merge(same, 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 734 ms 35984 KB Output is correct
3 Correct 698 ms 35836 KB Output is correct
4 Correct 676 ms 35760 KB Output is correct
5 Correct 698 ms 35756 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 35832 KB Output is correct
2 Correct 669 ms 35960 KB Output is correct
3 Correct 788 ms 36344 KB Output is correct
4 Correct 819 ms 36088 KB Output is correct
5 Correct 619 ms 36088 KB Output is correct
6 Correct 654 ms 35844 KB Output is correct
7 Correct 496 ms 30424 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 734 ms 35984 KB Output is correct
3 Correct 698 ms 35836 KB Output is correct
4 Correct 676 ms 35760 KB Output is correct
5 Correct 698 ms 35756 KB Output is correct
6 Correct 617 ms 35832 KB Output is correct
7 Correct 669 ms 35960 KB Output is correct
8 Correct 788 ms 36344 KB Output is correct
9 Correct 819 ms 36088 KB Output is correct
10 Correct 619 ms 36088 KB Output is correct
11 Correct 654 ms 35844 KB Output is correct
12 Correct 496 ms 30424 KB Output is correct
13 Correct 675 ms 35920 KB Output is correct
14 Correct 832 ms 61560 KB Output is correct
15 Correct 665 ms 53496 KB Output is correct
16 Correct 697 ms 57976 KB Output is correct
17 Correct 727 ms 59900 KB Output is correct
18 Correct 631 ms 53496 KB Output is correct
19 Correct 718 ms 53496 KB Output is correct
20 Correct 701 ms 53496 KB Output is correct
21 Correct 728 ms 54136 KB Output is correct
22 Correct 711 ms 53732 KB Output is correct
23 Correct 694 ms 54312 KB Output is correct
24 Correct 694 ms 60664 KB Output is correct
25 Correct 642 ms 53752 KB Output is correct