Submission #133482

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
133482	2019-07-20 21:59:05	thebes	Werewolf (IOI18_werewolf)	C++14	100 / 100	1014 ms	103148 KiB

werewolf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int MN = 4e5+5, LG = 20;
int ds[MN], p[MN], rep[MN], N, M, Q, i, j, vis[MN][2], nxt, sp[MN][LG], rev[MN], mp[MN], ans[MN];
struct edge{int x, y;}; vector<edge> ee;
vector<int> adj[MN];
int fnd(int x){return ds[x]=ds[x]==x?x:fnd(ds[x]);}
pair<int,int> a[MN]; set<int> st[MN];
struct qur{int s, r, id;}; vector<qur> q;
void dfs(int n){
    vis[n][0]=++nxt; rev[nxt]=n; mp[n]=nxt;
    sp[n][0]=p[n];
    for(auto v : adj[n])
        dfs(v);
    vis[n][1]=nxt;
}
int anc(int n,int h){
    for(int i=LG-1;i>=0;i--){
        if(sp[n][i]>=h) n=sp[n][i];
    }
    return n;
}
vector<int> check_validity(int n,vector<int> x,vector<int> y,vector<int> s,vector<int> e,vector<int> l,vector<int> r){
    N = n; M = x.size(); Q = s.size();
    for(i=0;i<M;i++) ee.push_back({x[i]+1,y[i]+1});
    for(i=0;i<Q;i++) s[i]++,e[i]++,l[i]++,r[i]++;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (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:32:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<ee.size();i++){if(ee[i].x<ee[i].y)swap(ee[i].x,ee[i].y);}
             ~^~~~~~~~~~
werewolf.cpp:54:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<ee.size();i++) swap(ee[i].x,ee[i].y);
             ~^~~~~~~~~~
werewolf.cpp:58:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i<q.size()&&q[i].r<v.y){
               ~^~~~~~~~~
werewolf.cpp:73:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i<q.size()){
           ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51