oj.uz

답안 #244200

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244200 2020-07-02T19:29:25 Z rqi 동기화 (JOI13_synchronization) C++14
100 / 100
 1621 ms 76756 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 
 
typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 
 
typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 
 
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
 
template<class T> bool ckmin(T& a, const T& b) { 
    return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
    return a < b ? a = b, 1 : 0; } 
int pct(int x) { return __builtin_popcount(x); } 
int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 
int fstTrue(function<bool(int)> f, int lo, int hi) {
    hi ++; assert(lo <= hi); // assuming f is increasing
    while (lo < hi) { // find first index such that f is true 
        int mid = (lo+hi)/2; 
        f(mid) ? hi = mid : lo = mid+1; 
    } 
    return lo;
}
 
// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);
 
template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
 
template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
 
// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
template<class A> str ts(complex<A> c) { 
    stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) { 
    str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
    res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
    str res = ""; F0R(i,SZ) res += char('0'+b[i]);
    return res; }
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) { // containers with begin(), end()
    bool fst = 1; str res = "{";
    for (const auto& x: v) {
        if (!fst) res += ", ";
        fst = 0; res += ts(x);
    }
    res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
    return "("+ts(p.f)+", "+ts(p.s)+")"; }
 
// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
    pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
    pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
 
// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << ts(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif
 
// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
    unsyncIO();
    // cin.exceptions(cin.failbit); 
    // throws exception when do smth illegal
    // ex. try to read letter into int
    if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}
 
const int mx = 200005;
int N, M, Q;
int ans[mx];
vi change[mx];
vpi bad[mx];
vpi adj[mx];
bool done[mx]; // processed as centroid yet
int sub[mx],cen[mx]; // subtree size, centroid anc
map<int,list<int>> to[mx], from[mx];

void dfs(int x, int p) { sub[x] = 1; 
    trav(y,adj[x]) if (!done[y.f] && y.f != p) 
    dfs(y.f,x), sub[x] += sub[y.f]; 
}
int centroid(int x) {
    dfs(x,-1); 
    for (int sz = sub[x];;) {
        pi mx = {0,0};
        trav(y,adj[x]) if (!done[y.f] && sub[y.f] < sub[x]) 
            ckmax(mx,{sub[y.f],y.f});
        if (mx.f*2 <= sz) return x; 
        x = mx.s;
    }
}

void ad(list<int>& a, list<int>& b) {
    a.splice(a.begin(), b);
}

void merge(map<int,list<int>>& a, map<int,list<int>>& b) {
    if(sz(a) < sz(b)) swap(a, b);
    for(auto &u: b){
        ad(a[u.f], u.s);
    }
    b.clear();
}
 
void getAll(list<int>& x, map<int,list<int>>& a, pi p) {
    while(true){
        auto it = a.lb(p.f+1);
        if(it == a.end() || it->f >= p.s) break;
        ad(x, it->s);
        a.erase(it->f);
    }
}

void genToFrom(int node, int prv = -1) {
    list<int> l1{node};
    list<int> l2{node};
    ad(to[node][1], l1);
    ad(from[node][M], l2);

    for(auto u: adj[node]){
        if(done[u.f]) continue;
        if(u.f == prv) continue;
        genToFrom(u.f, node);
        for(int j = 0; j < sz(bad[u.s]); j++){
            int r = bad[u.s][j].f;
            int l = bad[u.s][j].s;
            {
                list<int> z; //add bad stuff to here
                getAll(z, to[u.f], bad[u.s][j]);
                if(sz(z)) ad(to[node][l], z);
            }
            {
                list<int> z;
                getAll(z, from[u.f], bad[u.s][j]);
                if(sz(z)) ad(from[node][r], z);
            }
        }
        merge(to[node], to[u.f]);
        merge(from[node], from[u.f]);
        to[u.f].clear();
        from[u.f].clear();
    }
}

int comp[mx]; //component it belongs to

void makeLabel(int node, int prv, int cnt) { //assigns cnt to comp[] in a centroid subtree
    comp[node] = cnt;
    for(auto u: adj[node]){
        if(done[u.f]) continue;
        if(u.f == prv) continue;
        makeLabel(u.f, node, cnt);
    }
}

int genLabel(int x) { //generates different labels for each centroid subtree
    comp[x] = 0;
    int curlabel = 0;
    for(auto u: adj[x]){
        if(done[u.f]) continue;
        makeLabel(u.f, -1, ++curlabel);
    }
    return curlabel;
}


void gen(int CEN, int _x) { // CEN = centroid above x

    int x = centroid(_x); done[x] = 1; cen[x] = CEN; 
    sub[x] = sub[_x];
    //dbg(CEN, x);
    genToFrom(x);

    // dbg(to[x]);
    // dbg(from[x]);

    vi compans(genLabel(x)+1, 0);
    int cursum = 0; //shouldbe equal to current sum of compans
    auto it = to[x].begin();
    for(auto u: from[x]){
        while(it != to[x].end()){
            if(it->f <= u.f){   
                for(auto v: it->s){
                    compans[comp[v]]++;
                    cursum++;
                }
                it = next(it);
            }
            else break;
        }
        for(auto v: u.s){
            ans[v]+=cursum;
            //dbg(v, cursum);
            if(comp[v] > 0) ans[v]-=compans[comp[v]];
            //dbg(v, -compans[comp[v]]);
        }
    }

    to[x].clear();
    from[x].clear();
    
    trav(y,adj[x]) if (!done[y.f]) gen(x,y.f);
}


void init(int _N) { N = _N; FOR(i,1,N+1) done[i] = 0;
    gen(-1,1); } // start at vert 1

 
int main() {
    setIO();
    cin >> N >> M >> Q;
    for(int i = 1; i <= N-1; i++){
        int X, Y;
        cin >> X >> Y;
        adj[X].pb(mp(Y, i));
        adj[Y].pb(mp(X, i));
    }
    for(int i = 1; i <= N-1; i++){
        change[i].pb(-5);
    }
    for(int i = 1; i <= M; i++){
        int D;
        cin >> D;
        change[D].pb(i);
    }
    for(int i = 1; i <= N-1; i++){
        if(sz(change[i]) % 2 == 1){
            change[i].pb(M+5);
        }
    }
    for(int i = 1; i <= N-1; i++){
        for(int j = 0; j < sz(change[i]); j+=2){
            bad[i].pb(mp(change[i][j], change[i][j+1]));
        }
    }

    init(N);

    for(int i = 1; i <= Q; i++){
        int C;
        cin >> C;
        ps(ans[C]);
    }
 
    // you should actually read the stuff at the bottom
}
 
/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
*/

Compilation message

synchronization.cpp: In function 'void setIn(std::__cxx11::string)':
synchronization.cpp:128:31: 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); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
synchronization.cpp: In function 'void setOut(std::__cxx11::string)':
synchronization.cpp:129:32: 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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 33280 KB Output is correct
2 Correct 22 ms 33280 KB Output is correct
3 Correct 22 ms 33280 KB Output is correct
4 Correct 23 ms 33280 KB Output is correct
5 Correct 23 ms 33280 KB Output is correct
6 Correct 27 ms 33536 KB Output is correct
7 Correct 83 ms 35328 KB Output is correct
8 Correct 90 ms 35576 KB Output is correct
9 Correct 87 ms 35420 KB Output is correct
10 Correct 1114 ms 54776 KB Output is correct
11 Correct 1149 ms 54944 KB Output is correct
12 Correct 1557 ms 72980 KB Output is correct
13 Correct 393 ms 63468 KB Output is correct
14 Correct 1050 ms 55288 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 788 ms 68188 KB Output is correct
2 Correct 739 ms 67572 KB Output is correct
3 Correct 1473 ms 76024 KB Output is correct
4 Correct 1415 ms 76060 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 33280 KB Output is correct
2 Correct 22 ms 33280 KB Output is correct
3 Correct 26 ms 33280 KB Output is correct
4 Correct 26 ms 33280 KB Output is correct
5 Correct 25 ms 33280 KB Output is correct
6 Correct 31 ms 33664 KB Output is correct
7 Correct 114 ms 37240 KB Output is correct
8 Correct 1561 ms 73164 KB Output is correct
9 Correct 1593 ms 73124 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1591 ms 73200 KB Output is correct
2 Correct 1496 ms 76320 KB Output is correct
3 Correct 1528 ms 76708 KB Output is correct
4 Correct 1489 ms 76756 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 33408 KB Output is correct
2 Correct 24 ms 33280 KB Output is correct
3 Correct 22 ms 33280 KB Output is correct
4 Correct 23 ms 33280 KB Output is correct
5 Correct 30 ms 33408 KB Output is correct
6 Correct 86 ms 35448 KB Output is correct
7 Correct 1220 ms 54956 KB Output is correct
8 Correct 1621 ms 73080 KB Output is correct
9 Correct 400 ms 63592 KB Output is correct
10 Correct 1103 ms 55800 KB Output is correct
11 Correct 804 ms 67956 KB Output is correct
12 Correct 816 ms 68084 KB Output is correct
13 Correct 1565 ms 76720 KB Output is correct