제출 #916552

#제출 시각아이디문제언어결과실행 시간메모리
91655212345678늑대인간 (IOI18_werewolf)C++17
100 / 100
600 ms110100 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; const int nx=4e5+5; int dsu[nx], id[nx][2], idx, cnt, l[nx][2], r[nx][2], p[nx][2], res[nx]; vector<int> d[nx], a[nx], ans; vector<pair<int, int>> c[nx]; vector<tuple<int, int, int>> eds, edt; struct fenwick { int d[nx]; void add(int i) { while (i<nx) d[i]++, i+=(i&-i); } int find(int i) { int res=0; while (i>0) res+=d[i], i-=(i&-i); return res; } } f; int find(int x) { if (dsu[x]==x) return x; return dsu[x]=find(dsu[x]); } void dfs(int u, int m) { //cout<<"dfs "<<u<<'\n'; l[u][m]=INT_MAX; if (d[u].empty()) return id[u][m]=l[u][m]=r[u][m]=++cnt, void(); for (auto v:d[u]) dfs(v, m), l[u][m]=min(l[u][m], l[v][m]), r[u][m]=max(r[u][m], r[v][m]); } std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) { for (int i=0; i<X.size(); i++) if (X[i]<Y[i]) swap(X[i], Y[i]); for (int i=0; i<X.size(); i++) eds.push_back({Y[i], 0, X[i]}), edt.push_back({X[i], 0, Y[i]}); for (int i=0; i<S.size(); i++) eds.push_back({L[i], -1, i}), edt.push_back({R[i], 1, i}); sort(eds.begin(), eds.end()); reverse(eds.begin(), eds.end()); sort(edt.begin(), edt.end()); for (int i=0; i<2*N-1; i++) dsu[i]=i; idx=N; for (auto [u, t, v]:eds) { //cout<<"update "<<u<<' '<<t<<' '<<v<<'\n'; if (t==-1) p[v][0]=find(S[v]); //cout<<"find "<<v<<' '<<S[v]<<' '<<find(S[v])<<'\n'; else if (find(u)!=find(v)) d[idx].push_back(find(u)), d[idx].push_back(find(v)), dsu[find(u)]=dsu[find(v)]=idx++; //cout<<"add edge "<<u<<' '<<v<<' '<<idx<<'\n'; } dfs(idx-1, 0); idx=N; cnt=0; for (int i=0; i<2*N-1; i++) dsu[i]=i, d[i].clear(); for (auto [u, t, v]:edt) { //cout<<"update "<<u<<' '<<t<<' '<<v<<'\n'; if (t==1) p[v][1]=find(E[v]); //cout<<"find "<<v<<' '<<S[v]<<' '<<find(S[v])<<'\n'; else if (find(u)!=find(v)) d[idx].push_back(find(u)), d[idx].push_back(find(v)), dsu[find(u)]=dsu[find(v)]=idx++; //cout<<"add edge "<<u<<' '<<v<<' '<<idx<<'\n'; } dfs(idx-1, 1); /* cout<<"id "; for (int i=0; i<N; i++) cout<<id[i][1]<<' '; cout<<'\n'; for (int i=0; i<S.size(); i++) cout<<i<<' '<<p[i]<<' '<<l[p[i]][1]<<' '<<r[p[i]][1]<<'\n';*/ //for (int i=0; i<S.size(); i++) cout<<"range "<<i<<' '<<l[p[i]][0]<<' '<<l[p[i]][1]<<' '<<r[p[]i][0]<<' '<<r[i][1]<<'\n'; for (int i=0; i<S.size(); i++) c[l[p[i][0]][0]-1].push_back({-1, i}), c[r[p[i][0]][0]].push_back({1, i}); for (int i=0; i<N; i++) a[id[i][0]].push_back(id[i][1]); for (int i=0; i<=N; i++) { for (auto y:a[i]) f.add(y); for (auto [mul, j]:c[i]) res[j]+=(f.find(r[p[j][1]][1])-f.find(l[p[j][1]][1]-1))*mul; } for (int i=0; i<S.size(); i++) ans.push_back(res[i]>0); return ans; }

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

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i=0; i<X.size(); i++) if (X[i]<Y[i]) swap(X[i], Y[i]);
      |                   ~^~~~~~~~~
werewolf.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i=0; i<X.size(); i++) eds.push_back({Y[i], 0, X[i]}), edt.push_back({X[i], 0, Y[i]});
      |                   ~^~~~~~~~~
werewolf.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i=0; i<S.size(); i++) eds.push_back({L[i], -1, i}), edt.push_back({R[i], 1, i});
      |                   ~^~~~~~~~~
werewolf.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i=0; i<S.size(); i++) c[l[p[i][0]][0]-1].push_back({-1, i}), c[r[p[i][0]][0]].push_back({1, i});
      |                   ~^~~~~~~~~
werewolf.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i=0; i<S.size(); i++) ans.push_back(res[i]>0);
      |                   ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...