제출 #117046

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117046		eriksuenderhauf	Regions (IOI09_regions)	C++11	100 / 100	6384 ms	37064 KiB

regions

    #pragma GCC optimize("O3")
    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    #include <ext/rope>
    #define mem(a,v) memset((a), (v), sizeof (a))
    #define enl printf("\n")
    #define case(t) printf("Case #%d: ", (t))
    #define ni(n) scanf("%d", &(n))
    #define nl(n) scanf("%I64d", &(n))
    #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
    #define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
    #define pri(n) printf("%d\n", (n))
    #define prl(n) printf("%I64d\n", (n))
    #define pii pair<int, int>
    #define pil pair<int, long long>
    #define pll pair<long long, long long>
    #define vii vector<pii>
    #define vil vector<pil>
    #define vll vector<pll>
    #define vi vector<int>
    #define vl vector<long long>
    #define pb push_back
    #define mp make_pair
    #define fi first
    #define se second
    using namespace std;
    using namespace __gnu_pbds;
    typedef long long ll;
    typedef cc_hash_table<int,int,hash<int>> ht;
    typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
    const double pi = acos(-1);
    const int MOD = 1e9 + 7;
    const int INF = 1e9 + 7;
    const int MAXN = 2e5 + 5;
    const int MAXR = 3e4 + 5;
    const int MAGIC = 400;
    const double eps = 1e-9;
    int par[MAXN], col[MAXN], cnt[MAXN];
    vi ans[MAXR];
    vi adj[MAXN], ind[MAXR], idx[MAXR];
    int n, r, q, t = 0, st[MAXN], en[MAXN];
    map<pii,int> dp;
     
    void dfs(int u, int x, int d) {
    	int fl = 0;
    	if (col[u] == x)
    		fl++;
    	for (int v: adj[u])
    		dfs(v, x, d + fl);
    	ans[x][col[u]] += d;
    }
     
    void dfs(int u) {
    	st[u] = t++;
    	ind[col[u]].pb(st[u]);
    	idx[col[u]].pb(u);
    	for (int v: adj[u])
    		dfs(v);
    	en[u] = t;
    }
     
    int main() {
    	scanf("%d %d %d", &n, &r, &q);
    	scanf("%d", &col[0]);
    	for (int i = 1; i < n; i++) {
    		scanf("%d %d", &par[i], &col[i]);
    		adj[--par[i]].pb(i);
    		cnt[col[i]]++;
    	}
    	dfs(0);
    	for (int i = 1; i <= r; i++)
    		if (cnt[i] > MAGIC) {
    			ans[i].resize(r + 2);
    			dfs(0, i, 0);
    		}
    	while (q--) {
    		int x, y;
    		scanf("%d %d", &x, &y);
    		if (cnt[x] <= MAGIC) {
    			if (dp.count(mp(x, y))) {
    				printf("%d\n", dp[mp(x, y)]);
              		fflush(stdout);
    				continue;
    			}
    			int anscnt = 0;
    			for (int j = 0; j < idx[x].size(); j++) {
    				int lo = lower_bound(ind[y].begin(), ind[y].end(), st[idx[x][j]]) - ind[y].begin();
    				int hi = lower_bound(ind[y].begin(), ind[y].end(), en[idx[x][j]]) - ind[y].begin();
    				anscnt += hi - lo;
    			}
    			printf("%d\n", anscnt);
              	fflush(stdout);
    			dp[mp(x, y)] = anscnt;
    		} else {
    			printf("%d\n", ans[x][y]);
              	fflush(stdout);
    		}
    	}
    	return 0;
    }

컴파일 시 표준 에러 (stderr) 메시지

regions.cpp: In function 'int main()':
regions.cpp:87:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for (int j = 0; j < idx[x].size(); j++) {
                        ~~^~~~~~~~~~~~~~~
regions.cpp:64:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d %d %d", &n, &r, &q);
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:65:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &col[0]);
      ~~~~~^~~~~~~~~~~~~~~
regions.cpp:67:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &par[i], &col[i]);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:79:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &x, &y);
       ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85