# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
987427 | 2024-05-22T18:13:31 Z | activedeltorre | 참나무 (IOI23_beechtree) | C++17 | 2000 ms | 62304 KB |
#include "beechtree.h" #include <vector> #include <queue> #include <iostream> #include <map> #include <algorithm> using namespace std; vector<int>cop[200005]; int cul[200005]; int imp[200005]; int dist[200005]; int par[200005]; vector<int>vecus; map<int,int>mp; map<int,int>mp2; map<int,int>fre; long long mod=1e9+7; long long has[200005]; vector<long long> vactoriceanu[510]; int nmax=500; int calc(int curr) { mp2.clear(); fre.clear(); int cur; queue<int>qu; dist[curr]=0; qu.push(curr); vecus.clear(); for(int i=1;i<=nmax;i++) { vactoriceanu[i].clear(); } while(qu.size()) { cur=qu.front(); vecus.push_back(cur); qu.pop(); for(auto k:cop[cur]) { dist[k]=dist[curr]+1; qu.push(k); } } int posible=0; for(auto i:vecus) { if(i!=curr) { fre[cul[i]]++; vactoriceanu[fre[cul[i]]].push_back(cul[i]); } mp2[has[i]]++; posible=max(posible,imp[i]); } for(int i=1;i<=nmax;i++) { sort(vactoriceanu[i].begin(),vactoriceanu[i].end()); long long val=0; for(auto j:vactoriceanu[i]) { val=(val*23+j+13)%mod; } if(val!=0) { if(mp2[val]==0) { return 0; } else { mp2[val]--; } } vactoriceanu[i].clear(); } if(posible==1) { return 0; } return 1; } map<pair<int,int> ,int >frevals; std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C) { int n=N,culs=M,i; vector<int>ans; for(i=1;i<n;i++) { par[i]=P[i]; cop[P[i]].push_back(i); cul[i]=C[i]; } for(i=0;i<n;i++) { for(auto k:cop[i]) { has[i]=(has[i]*23+cul[k]+13)%mod; frevals[{i,cul[k]}]++; } for(auto k:cop[i]) { for(auto j:cop[k]) { if(frevals[{k,cul[j]}]>frevals[{i,cul[j]}]) { imp[i]=1; } } } } for(i=0;i<n ;i++) { ans.push_back(calc(i)); } return ans; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4952 KB | Output is correct |
2 | Correct | 3 ms | 4956 KB | Output is correct |
3 | Incorrect | 3 ms | 4956 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4952 KB | Output is correct |
2 | Correct | 3 ms | 4956 KB | Output is correct |
3 | Correct | 4 ms | 4956 KB | Output is correct |
4 | Correct | 3 ms | 4956 KB | Output is correct |
5 | Correct | 3 ms | 4956 KB | Output is correct |
6 | Correct | 3 ms | 5092 KB | Output is correct |
7 | Correct | 3 ms | 4956 KB | Output is correct |
8 | Incorrect | 4 ms | 5160 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
9 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4952 KB | Output is correct |
2 | Correct | 3 ms | 4956 KB | Output is correct |
3 | Correct | 4 ms | 4956 KB | Output is correct |
4 | Correct | 3 ms | 4956 KB | Output is correct |
5 | Correct | 3 ms | 4956 KB | Output is correct |
6 | Correct | 3 ms | 5092 KB | Output is correct |
7 | Execution timed out | 2028 ms | 62304 KB | Time limit exceeded |
8 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 4952 KB | 2nd lines differ - on the 2nd token, expected: '1', found: '0' |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4952 KB | Output is correct |
2 | Correct | 3 ms | 4956 KB | Output is correct |
3 | Correct | 3 ms | 4956 KB | Output is correct |
4 | Incorrect | 4 ms | 5160 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4952 KB | Output is correct |
2 | Correct | 3 ms | 4956 KB | Output is correct |
3 | Incorrect | 3 ms | 4956 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4952 KB | Output is correct |
2 | Correct | 3 ms | 4956 KB | Output is correct |
3 | Correct | 3 ms | 4956 KB | Output is correct |
4 | Incorrect | 4 ms | 5160 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4952 KB | Output is correct |
2 | Correct | 3 ms | 4956 KB | Output is correct |
3 | Incorrect | 3 ms | 4956 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4952 KB | Output is correct |
2 | Correct | 3 ms | 4956 KB | Output is correct |
3 | Correct | 3 ms | 4956 KB | Output is correct |
4 | Incorrect | 4 ms | 5160 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4952 KB | Output is correct |
2 | Correct | 3 ms | 4956 KB | Output is correct |
3 | Incorrect | 3 ms | 4956 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
4 | Halted | 0 ms | 0 KB | - |