oj.uz

Submission #270676

# Submission time Handle Problem Language Result Execution time Memory
270676 2020-08-17T22:34:15 Z fivefourthreeone Izlet (COI19_izlet) C++17
43 / 100
 800 ms 36088 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) {
            if(node==-1)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 665 ms 35892 KB Output is correct
3 Correct 657 ms 35832 KB Output is correct
4 Correct 679 ms 35824 KB Output is correct
5 Correct 667 ms 35776 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 35884 KB Output is correct
2 Correct 665 ms 35960 KB Output is correct
3 Correct 783 ms 36088 KB Output is correct
4 Correct 800 ms 36088 KB Output is correct
5 Correct 636 ms 35960 KB Output is correct
6 Correct 641 ms 35960 KB Output is correct
7 Correct 512 ms 30456 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 665 ms 35892 KB Output is correct
3 Correct 657 ms 35832 KB Output is correct
4 Correct 679 ms 35824 KB Output is correct
5 Correct 667 ms 35776 KB Output is correct
6 Correct 620 ms 35884 KB Output is correct
7 Correct 665 ms 35960 KB Output is correct
8 Correct 783 ms 36088 KB Output is correct
9 Correct 800 ms 36088 KB Output is correct
10 Correct 636 ms 35960 KB Output is correct
11 Correct 641 ms 35960 KB Output is correct
12 Correct 512 ms 30456 KB Output is correct
13 Incorrect 633 ms 36048 KB Output isn't correct
14 Halted 0 ms 0 KB -