| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 295955 |
2020-09-10T06:35:02 Z |
Hemimor |
Regions (IOI09_regions) |
C++14 |
|
152 ms |
49528 KB |
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
class Segment_Tree{
private:
int n;
vi date;
public:
Segment_Tree(int n_){
n=1;
while(n<n_) n*=2;
date=vi(2*n-1);
}
void Update(int k,int x){
k+=n-1;
date[k]+=x;
while(k>0){
k=(k-1)/2;
date[k]=date[k*2+1]+date[k*2+2];
}
}
int Query(int a,int b){
a+=n-1;b+=n-1;
int m=0;
while(a<b){
if(a%2==0) m+=date[a++];
if(b%2==0) m+=date[--b];
a/=2;b/=2;
}
return m;
}
int Open(int k){return date[k+n-1];}
};
const int M=25000;
int n,m,q,id=0;
vvi g,b;
vi a,par,num,lt,rt,c,d;
map<P,int> mp;
void dfs(int v){
lt[v]=id++;
for(auto u:g[v]) dfs(u);
rt[v]=id;
}
void DFS(int v,int t){
if(a[v]==t){
c[v]++;
d[v]++;
}
for(auto u:g[v]){
d[u]=d[v];
DFS(u,t);
c[v]+=c[u];
}
}
int main(){
scanf("%d%d%d",&n,&m,&q);
Segment_Tree st(n);
g=vvi(n);
b=vvi(m);
a=lt=rt=vi(n);
par=vi(n,-1);
num=vi(m);
for(int i=0;i<n;i++){
if(i){
scanf("%d",&par[i]);
par[i]--;
g[par[i]].push_back(i);
}
scanf("%d",&a[i]);
a[i]--;
num[a[i]]++;
b[a[i]].push_back(i);
}
dfs(0);
for(int i=0;i<m;i++) if(a[i]>M){
c=d=vi(n);
DFS(0,i);
vi tc(m),td(m);
for(int j=0;j<n;j++) if(a[j]!=i){
tc[a[j]]+=c[j];
td[a[j]]+=d[j];
}
for(int j=0;j<m;j++) if(j!=i){
mp[{j,i}]=tc[j];
mp[{i,j}]=td[j];
}
}
assert(0);
for(int i=0;i<q;i++){
int x,y,res=0;
scanf("%d%d",&x,&y);
x--,y--;
if(mp.find({x,y})!=mp.end()) res=mp[{x,y}];
else{
for(auto j:b[y]) st.Update(lt[j],1);
for(auto j:b[x]) res+=st.Query(lt[j],rt[j]);
for(auto j:b[y]) st.Update(lt[j],-1);
}
mp[{x,y}]=res;
printf("%d\n",res);
fflush(stdout);
}
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
94 | scanf("%d%d%d",&n,&m,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:103:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
103 | scanf("%d",&par[i]);
| ~~~~~^~~~~~~~~~~~~~
regions.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
107 | scanf("%d",&a[i]);
| ~~~~~^~~~~~~~~~~~
regions.cpp:129:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
129 | scanf("%d%d",&x,&y);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
1 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
2 ms |
768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
2 ms |
768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
4 ms |
1664 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
8 ms |
2304 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
15 ms |
3072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
13 ms |
4352 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
15 ms |
4096 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
20 ms |
5368 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
27 ms |
10232 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
14712 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
56 ms |
13048 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
61 ms |
18488 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
20 ms |
5632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
30 ms |
9216 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
36 ms |
9720 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
54 ms |
13816 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
66 ms |
23160 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
110 ms |
29816 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
137 ms |
38904 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
141 ms |
32632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
149 ms |
35192 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
133 ms |
34940 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
147 ms |
35320 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
144 ms |
42272 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
152 ms |
49528 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
145 ms |
47608 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
