Submission #414905

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
414905	2021-05-31T10:33:16 Z	Pro_ktmr	스파이 (JOI13_spy)	C++17	100 / 100	466 ms	11392 KB

spy

#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)

int N, M;
int parA[2000], parB[2000];
vector<int> chiA[2000], chiB[2000];

int cnt = 0;
int pre[2000], pos[2000];
void dfs(int n){
	pre[n] = cnt;
	cnt++;
	rep(i, chiA[n].size()) dfs(chiA[n][i]);
	pos[n] = cnt;
}

void dfs2(int n, vector<int>* v){
	v->pb(pre[n]);
	rep(i, chiB[n].size()) dfs2(chiB[n][i], v);
}

vector<pair<int, int>> query[2000];
int ans[2000] ={};

signed main(){
	cin >> N >> M;
	rep(i, N){
		int a, b;
		cin >> a >> b;
		parA[i] = a-1;
		if(a-1 >= 0) chiA[a-1].pb(i);
		parB[i] = b-1;
		if(b-1 >= 0) chiB[b-1].pb(i);
	}
	rep(i, N)
		if(parA[i] == -1) dfs(i);
	rep(i, M){
		int a, b;
		cin >> a >> b;
		query[b-1].pb({ a-1,i });
	}
	rep(i, N){
		vector<int> v;
		dfs2(i, &v);
		sort(all(v));
		vector<int> imos(v.size()+1, 0);
		rep(j, query[i].size()){
			int lederA = query[i][j].first;
			int l = pre[lederA];
			int r = pos[lederA];
			imos[lower_bound(all(v), l)-v.begin()]++;
			imos[lower_bound(all(v), r)-v.begin()]--;
		}
		rep(j, v.size()){
			if(j > 0) imos[j] += imos[j-1];
			ans[v[j]] += imos[j];
		}
	}
	rep(i, N) cout << ans[pre[i]] << endl;
}

Compilation message

spy.cpp: In function 'void dfs(int)':
spy.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
spy.cpp:19:2: note: in expansion of macro 'rep'
   19 |  rep(i, chiA[n].size()) dfs(chiA[n][i]);
      |  ^~~
spy.cpp: In function 'void dfs2(int, std::vector<int>*)':
spy.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
spy.cpp:25:2: note: in expansion of macro 'rep'
   25 |  rep(i, chiB[n].size()) dfs2(chiB[n][i], v);
      |  ^~~
spy.cpp: In function 'int main()':
spy.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
spy.cpp:33:2: note: in expansion of macro 'rep'
   33 |  rep(i, N){
      |  ^~~
spy.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
spy.cpp:41:2: note: in expansion of macro 'rep'
   41 |  rep(i, N)
      |  ^~~
spy.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
spy.cpp:43:2: note: in expansion of macro 'rep'
   43 |  rep(i, M){
      |  ^~~
spy.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
spy.cpp:48:2: note: in expansion of macro 'rep'
   48 |  rep(i, N){
      |  ^~~
spy.cpp:8:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
spy.cpp:53:3: note: in expansion of macro 'rep'
   53 |   rep(j, query[i].size()){
      |   ^~~
spy.cpp:8:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
spy.cpp:60:3: note: in expansion of macro 'rep'
   60 |   rep(j, v.size()){
      |   ^~~
spy.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
spy.cpp:65:2: note: in expansion of macro 'rep'
   65 |  rep(i, N) cout << ans[pre[i]] << endl;
      |  ^~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	460 KB	Output is correct
2	Correct	3 ms	460 KB	Output is correct
3	Correct	2 ms	460 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	2 ms	460 KB	Output is correct
6	Correct	2 ms	460 KB	Output is correct
7	Correct	2 ms	460 KB	Output is correct
8	Correct	2 ms	460 KB	Output is correct
9	Correct	1 ms	460 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	796 KB	Output is correct
2	Correct	165 ms	788 KB	Output is correct
3	Correct	7 ms	588 KB	Output is correct
4	Correct	7 ms	560 KB	Output is correct
5	Correct	9 ms	588 KB	Output is correct
6	Correct	8 ms	588 KB	Output is correct
7	Correct	41 ms	744 KB	Output is correct
8	Correct	10 ms	588 KB	Output is correct

Subtask #3

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	465 ms	11392 KB	Output is correct
2	Correct	466 ms	10012 KB	Output is correct
3	Correct	343 ms	10092 KB	Output is correct
4	Correct	321 ms	10308 KB	Output is correct
5	Correct	304 ms	10856 KB	Output is correct
6	Correct	289 ms	9600 KB	Output is correct
7	Correct	383 ms	11304 KB	Output is correct
8	Correct	320 ms	11204 KB	Output is correct