oj.uz

답안 #79460

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
79460 2018-10-14T01:52:15 Z Benq Pictionary (COCI18_pictionary) C++14
140 / 140
 186 ms 18080 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
// const int MX = 100001;

/**
* Description: more convenient functions for input / output
  * experimentation with C++11 features
*/

namespace io {
    template<typename Test, template<typename...> class Ref>
    struct is_specialization : std::false_type {};

    template<template<typename...> class Ref, typename... Args>
    struct is_specialization<Ref<Args...>, Ref>: std::true_type {};
    // https://stackoverflow.com/questions/16337610/how-to-know-if-a-type-is-a-specialization-of-stdvector

    void setIn(string s) { freopen(s.c_str(),"r",stdin); }
    void setOut(string s) { freopen(s.c_str(),"w",stdout); }
    void setIO(string s = "") {
        ios_base::sync_with_stdio(0); cin.tie(0);
        if (sz(s)) { setIn(s+".in"), setOut(s+".out"); }
    }
    
    // INPUT 
    
    // double input seems slow on CF
    void re(double& x) { string t; cin >> t; x = stod(t); } 
    void re(ld& x) { string t; cin >> t; x = stold(t); }
    template<class T> void re(T& x) { cin >> x; }
    template<class Arg, class... Args> void re(Arg& first, Args&... rest) { 
        re(first); re(rest...); 
    }
    template<class T1, class T2> istream& operator>>(istream& is, pair<T1,T2>& p) {
        is >> p.f >> p.s; return is;
    }
    template<class T> istream& operator>>(istream& is, vector<T>& a) {
        F0R(i,sz(a)) is >> a[i];
        return is;
    }
    
    // OUTPUT 
    
    template<class T> void pr(const T& x) { cout << x << '\n'; }
    template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) { 
        cout << first << ' '; pr(rest...); 
    }
    template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) {
        os << '{' << a.f << ", " << a.s << '}'; return os;
    }
    template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {
        os << '{';
        F0R(i,sz(a)) {
            if (i) {
                os << ", ";
                if (is_specialization<T, vector>::value) os << '\n';
            }
            os << a[i];
        }
        os << '}';
        return os;
    }
}

using namespace io;

template<int SZ> struct DSU {
    int par[SZ], sz[SZ];
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) return 0;
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], par[y] = x;
    	return 1;
    }
};

template<int SZ> struct queryConnect {
    int n,q; // vertices, edges, # queries
    vpi ed; // edges

    pi p[SZ]; // connectivity queries 
    int l[SZ],r[SZ]; // left and right bounds for answer
    vi tri[SZ];

    bool left() {
        F0R(i,sz(ed)+1) tri[i].clear();
        bool ok = 0;
        F0R(i,q) if (l[i] != r[i]) {
            tri[(l[i]+r[i])/2].pb(i);
            ok = 1;
        }
        return ok;
    }

    void test() {
        DSU<SZ> D = DSU<SZ>();
        F0R(i,sz(ed)+1) {
            if (i) D.unite(ed[i-1].f,ed[i-1].s);
            for (int x: tri[i]) {
                if (D.get(p[x].f) == D.get(p[x].s)) r[x] = i;
                else l[x] = i+1;
            }
        }
    }
     
    void solve() {
        F0R(i,q) l[i] = 0, r[i] = sz(ed)+1;
        while (left()) test();
    }
};

DSU<100001> D;
queryConnect<100001> Q;

int m;

int main() {
    setIO();
    re(Q.n,m,Q.q);
    
    FOR(i,1,m+1) {
        int t = m+1-i;
        for (int j = t; j+t <= Q.n; j += t) if (D.unite(j,j+t)) Q.ed.pb({j,j+t});
    }
    
    // cout << sz(Q.ed) << "\n";
    // exit(0);
    
    F0R(i,Q.q) {
        re(Q.p[i]);
        // Q.p[i] = {rand() % 100000+1, rand() % 100000+1};
    }
    Q.solve();
    
    F0R(i,Q.q) {
        if (Q.l[i] == 0) {
            cout << "0\n";
        } else {
            Q.l[i] --;
            cout << m+1-__gcd(Q.ed[Q.l[i]].f,Q.ed[Q.l[i]].s) << "\n";
        }
    }
}

/* 
* (Actually read this pls)
    * Rlly bad errors: int overflow, array bounds
    * Less bad errors: special cases (n=1?), set tle
    * Common sense: do smth instead of nothing
*/

Compilation message

pictionary.cpp: In function 'void io::setIn(std::__cxx11::string)':
pictionary.cpp:61:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
pictionary.cpp: In function 'void io::setOut(std::__cxx11::string)':
pictionary.cpp:62:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 5368 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 6268 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 9156 KB Output is correct
2 Correct 48 ms 9332 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 11220 KB Output is correct
2 Correct 59 ms 11220 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 11220 KB Output is correct
2 Correct 60 ms 11220 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 11220 KB Output is correct
2 Correct 72 ms 11220 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 12808 KB Output is correct
2 Correct 97 ms 12808 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 14856 KB Output is correct
2 Correct 131 ms 14856 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 15872 KB Output is correct
2 Correct 160 ms 16288 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 18080 KB Output is correct
2 Correct 186 ms 18080 KB Output is correct