답안 #727481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
727481	2023-04-20T21:00:32 Z	CutSandstone	Regions (IOI09_regions)	Java 11	컴파일 오류	0 ms	0 KB

regions

// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx,avx2")
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define f first
#define s second
#define pb push_back
#define inf ~((long long)1<<63)
using namespace std;
const int mod = 1000000007;
void setio(string name = "") { 
    ios::sync_with_stdio(false), cin.tie(nullptr); 
    if(name.length()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
class BIT {
  private:
    int size;
    vector<int> bit;
    vector<int> arr;

  public:
    BIT(int size) : size(size), bit(size + 1), arr(size) {}
    void set(int ind, int val) { add(ind, val - arr[ind]); }
    void add(int ind, int val) {
        arr[ind] += val;
        ind++;
        for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
    }
    int prev(int ind) {
        ind++;
        int total = 0;
        for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
        return total;
    }
    int sum(int a, int b){
        return prev(b)-(a == 0 ? 0:prev(a-1));
    }
};
int N, R, timer = 0;
vector<vector<int>> cnt;
vector<int> big;
vector<vector<int>> precomp;
vector<int> st, en;
vector<vector<int>> g;
vector<vector<int>> above;
vector<int> ans;
vector<int> nums;
vector<BIT> sums;
void dfs(int s, vector<int> curr, vector<stack<int>> last){
    ans[s] = ++curr[nums[s]];
    if(big[nums[s]]+1) last[big[nums[s]]].push(s);
    else for(int i = 0; i<last.size(); i++) above[s][i] = last[i].empty() ? -1:last[i].top();
    st[s] = timer++;
    for(int i: g[s]) dfs(i, curr, last);
    if(big[nums[s]]+1) last[big[nums[s]]].pop();
    curr[nums[s]]--;
    en[s] = timer-1;
}
void getComp(int size){
    precomp.resize(size, vector<int>(size, 0));
    vector<int> b(size);
    for(int i = R-1; i>=0; i--) if(big[i]+1) b[--size] = i;
    for(int i = 0; i<b.size(); i++){
        for(int j: cnt[b[i]])
            sums[i].set(st[j], 1);
        for(int j = 0; j<b.size(); j++) for(int k: cnt[b[j]]) 
            precomp[j][i]+=sums[i].sum(st[k], en[k])-(j == i ? 1:0);
    }
}
int main() {
    setio();
    int Q; cin >> N >> R >> Q;
    g.resize(N, vector<int>(0));
    nums.resize(N);
    cin >> nums[0];
    for(int i = 1; i<N; i++){
        int par; cin >> par;
        g[par-1].pb(i);
        cin >> nums[i];
    }
    cnt.resize(R, vector<int>(0));
    for(int i = 0; i<N; i++) cnt[--nums[i]].pb(i);
    int sqrt = 1;
    while(sqrt*sqrt <= N) sqrt++; sqrt--;
    while((R/sqrt)*N > 50000000) sqrt++;
    big.resize(R, -1);
    int p = 0;
    for(int i = 0; i<R; i++) if(cnt[i].size() >= sqrt) big[i] = p++;
    st.resize(N);
    en.resize(N);
    ans.resize(N);
    above.resize(N, vector<int>(p));
    dfs(0, vector<int>(R), vector<stack<int>>(p));
    sums.resize(p, BIT(N));
    getComp(p);
    BIT b(N);
    while(Q--> 0){
        int up, down; cin >> up >> down; --up, --down;
        if(big[up]+1 && big[down]+1) cout << precomp[big[up]][big[down]] << endl;
        else if(big[up]+1){
            int ret = 0;
            for(int i: cnt[down]){
                int u = above[i][big[up]];
                if(u != -1) ret+=ans[u];
            }
            cout << ret << endl;
        }else if(big[down]+1){
            int ret = 0;
            for(int i: cnt[up]) ret+=sums[big[down]].sum(st[i], en[i]);
           cout << ret << endl;
        }else{
           int ret = 0;
           for(int i: cnt[down]) b.set(st[i], 1);
           for(int i: cnt[up]) ret+=b.sum(st[i], en[i])-(up == down ? 1:0);
           for(int i: cnt[down]) b.set(st[i], 0);
           cout << ret << endl;
        }
    }
}

Compilation message

regions.java:3: error: illegal character: '#'
#include <bits/stdc++.h>
^
regions.java:3: error: class, interface, or enum expected
#include <bits/stdc++.h>
         ^
regions.java:4: error: illegal character: '#'
#define ll long long
^
regions.java:5: error: illegal character: '#'
#define vi vector<int>
^
regions.java:6: error: illegal character: '#'
#define f first
^
regions.java:7: error: illegal character: '#'
#define s second
^
regions.java:8: error: illegal character: '#'
#define pb push_back
^
regions.java:9: error: illegal character: '#'
#define inf ~((long long)1<<63)
^
regions.java:11: error: class, interface, or enum expected
const int mod = 1000000007;
^
regions.java:12: error: class, interface, or enum expected
void setio(string name = "") { 
^
regions.java:14: error: class, interface, or enum expected
    if(name.length()) {
    ^
regions.java:16: error: class, interface, or enum expected
        freopen((name + ".out").c_str(), "w", stdout);
        ^
regions.java:17: error: class, interface, or enum expected
    }
    ^
regions.java:20: error: illegal start of type
  private:
         ^
regions.java:25: error: illegal start of type
  public:
        ^
regions.java:26: error: ';' expected
    BIT(int size) : size(size), bit(size + 1), arr(size) {}
                 ^
regions.java:43: error: class, interface, or enum expected
int N, R, timer = 0;
^
regions.java:44: error: class, interface, or enum expected
vector<vector<int>> cnt;
^
regions.java:45: error: class, interface, or enum expected
vector<int> big;
^
regions.java:46: error: class, interface, or enum expected
vector<vector<int>> precomp;
^
regions.java:47: error: class, interface, or enum expected
vector<int> st, en;
^
regions.java:48: error: class, interface, or enum expected
vector<vector<int>> g;
^
regions.java:49: error: class, interface, or enum expected
vector<vector<int>> above;
^
regions.java:50: error: class, interface, or enum expected
vector<int> ans;
^
regions.java:51: error: class, interface, or enum expected
vector<int> nums;
^
regions.java:52: error: class, interface, or enum expected
vector<BIT> sums;
^
regions.java:53: error: class, interface, or enum expected
void dfs(int s, vector<int> curr, vector<stack<int>> last){
^
regions.java:55: error: class, interface, or enum expected
    if(big[nums[s]]+1) last[big[nums[s]]].push(s);
    ^
regions.java:56: error: class, interface, or enum expected
    else for(int i = 0; i<last.size(); i++) above[s][i] = last[i].empty() ? -1:last[i].top();
    ^
regions.java:56: error: class, interface, or enum expected
    else for(int i = 0; i<last.size(); i++) above[s][i] = last[i].empty() ? -1:last[i].top();
                        ^
regions.java:56: error: class, interface, or enum expected
    else for(int i = 0; i<last.size(); i++) above[s][i] = last[i].empty() ? -1:last[i].top();
                                       ^
regions.java:57: error: class, interface, or enum expected
    st[s] = timer++;
    ^
regions.java:58: error: class, interface, or enum expected
    for(int i: g[s]) dfs(i, curr, last);
    ^
regions.java:59: error: class, interface, or enum expected
    if(big[nums[s]]+1) last[big[nums[s]]].pop();
    ^
regions.java:60: error: class, interface, or enum expected
    curr[nums[s]]--;
    ^
regions.java:61: error: class, interface, or enum expected
    en[s] = timer-1;
    ^
regions.java:62: error: class, interface, or enum expected
}
^
regions.java:65: error: class, interface, or enum expected
    vector<int> b(size);
    ^
regions.java:66: error: class, interface, or enum expected
    for(int i = R-1; i>=0; i--) if(big[i]+1) b[--size] = i;
    ^
regions.java:66: error: class, interface, or enum expected
    for(int i = R-1; i>=0; i--) if(big[i]+1) b[--size] = i;
                     ^
regions.java:66: error: class, interface, or enum expected
    for(int i = R-1; i>=0; i--) if(big[i]+1) b[--size] = i;
                           ^
regions.java:67: error: class, interface, or enum expected
    for(int i = 0; i<b.size(); i++){
    ^
regions.java:67: error: class, interface, or enum expected
    for(int i = 0; i<b.size(); i++){
                   ^
regions.java:67: error: class, interface, or enum expected
    for(int i = 0; i<b.size(); i++){
                               ^
regions.java:70: error: class, interface, or enum expected
        for(int j = 0; j<b.size(); j++) for(int k: cnt[b[j]]) 
        ^
regions.java:70: error: class, interface, or enum expected
        for(int j = 0; j<b.size(); j++) for(int k: cnt[b[j]]) 
                       ^
regions.java:70: error: class, interface, or enum expected
        for(int j = 0; j<b.size(); j++) for(int k: cnt[b[j]]) 
                                   ^
regions.java:72: error: class, interface, or enum expected
    }
    ^
regions.java:76: error: class, interface, or enum expected
    int Q; cin >> N >> R >> Q;
    ^
regions.java:76: error: class, interface, or enum expected
    int Q; cin >> N >> R >> Q;
           ^
regions.java:77: error: class, interface, or enum expected
    g.resize(N, vector<int>(0));
    ^
regions.java:78: error: class, interface, or enum expected
    nums.resize(N);
    ^
regions.java:79: error: class, interface, or enum expected
    cin >> nums[0];
    ^
regions.java:80: error: class, interface, or enum expected
    for(int i = 1; i<N; i++){
    ^
regions.java:80: error: class, interface, or enum expected
    for(int i = 1; i<N; i++){
                   ^
regions.java:80: error: class, interface, or enum expected
    for(int i = 1; i<N; i++){
                        ^
regions.java:81: error: class, interface, or enum expected
        int par; cin >> par;
                 ^
regions.java:82: error: class, interface, or enum expected
        g[par-1].pb(i);
        ^
regions.java:83: error: class, interface, or enum expected
        cin >> nums[i];
        ^
regions.java:84: error: class, interface, or enum expected
    }
    ^
regions.java:86: error: class, interface, or enum expected
    for(int i = 0; i<N; i++) cnt[--nums[i]].pb(i);
    ^
regions.java:86: error: class, interface, or enum expected
    for(int i = 0; i<N; i++) cnt[--nums[i]].pb(i);
                   ^
regions.java:86: error: class, interface, or enum expected
    for(int i = 0; i<N; i++) cnt[--nums[i]].pb(i);
                        ^
regions.java:87: error: class, interface, or enum expected
    int sqrt = 1;
    ^
regions.java:88: error: class, interface, or enum expected
    while(sqrt*sqrt <= N) sqrt++; sqrt--;
    ^
regions.java:88: error: class, interface, or enum expected
    while(sqrt*sqrt <= N) sqrt++; sqrt--;
                                  ^
regions.java:89: error: class, interface, or enum expected
    while((R/sqrt)*N > 50000000) sqrt++;
    ^
regions.java:90: error: class, interface, or enum expected
    big.resize(R, -1);
    ^
regions.java:91: error: class, interface, or enum expected
    int p = 0;
    ^
regions.java:92: error: class, interface, or enum expected
    for(int i = 0; i<R; i++) if(cnt[i].size() >= sqrt) big[i] = p++;
    ^
regions.java:92: error: class, interface, or enum expected
    for(int i = 0; i<R; i++) if(cnt[i].size() >= sqrt) big[i] = p++;
                   ^
regions.java:92: error: class, interface, or enum expected
    for(int i = 0; i<R; i++) if(cnt[i].size() >= sqrt) big[i] = p++;
                        ^
regions.java:93: error: class, interface, or enum expected
    st.resize(N);
    ^
regions.java:94: error: class, interface, or enum expected
    en.resize(N);
    ^
regions.java:95: error: class, interface, or enum expected
    ans.resize(N);
    ^
regions.java:96: error: class, interface, or enum expected
    above.resize(N, vector<int>(p));
    ^
regions.java:97: error: class, interface, or enum expected
    dfs(0, vector<int>(R), vector<stack<int>>(p));
    ^
regions.java:98: error: class, interface, or enum expected
    sums.resize(p, BIT(N));
    ^
regions.java:99: error: class, interface, or enum expected
    getComp(p);
    ^
regions.java:100: error: class, interface, or enum expected
    BIT b(N);
    ^
regions.java:101: error: class, interface, or enum expected
    while(Q--> 0){
    ^
regions.java:102: error: class, interface, or enum expected
        int up, down; cin >> up >> down; --up, --down;
                      ^
regions.java:102: error: class, interface, or enum expected
        int up, down; cin >> up >> down; --up, --down;
                                         ^
regions.java:103: error: class, interface, or enum expected
        if(big[up]+1 && big[down]+1) cout << precomp[big[up]][big[down]] << endl;
        ^
regions.java:104: error: class, interface, or enum expected
        else if(big[up]+1){
        ^
regions.java:106: error: class, interface, or enum expected
            for(int i: cnt[down]){
            ^
regions.java:108: error: class, interface, or enum expected
                if(u != -1) ret+=ans[u];
                ^
regions.java:109: error: class, interface, or enum expected
            }
            ^
regions.java:111: error: class, interface, or enum expected
        }else if(big[down]+1){
        ^
regions.java:113: error: class, interface, or enum expected
            for(int i: cnt[up]) ret+=sums[big[down]].sum(st[i], en[i]);
            ^
regions.java:114: error: class, interface, or enum expected
           cout << ret << endl;
           ^
regions.java:115: error: class, interface, or enum expected
        }else{
        ^
regions.java:117: error: class, interface, or enum expected
           for(int i: cnt[down]) b.set(st[i], 1);
           ^
regions.java:118: error: class, interface, or enum expected
           for(int i: cnt[up]) ret+=b.sum(st[i], en[i])-(up == down ? 1:0);
           ^
regions.java:119: error: class, interface, or enum expected
           for(int i: cnt[down]) b.set(st[i], 0);
           ^
regions.java:120: error: class, interface, or enum expected
           cout << ret << endl;
           ^
regions.java:121: error: class, interface, or enum expected
        }
        ^
97 errors