oj.uz

답안 #68228

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
68228 2018-08-16T09:14:18 Z top34051 동기화 (JOI13_synchronization) C++17
40 / 100
 8000 ms 50060 KB 
//subtask 1
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 2e5 + 5;

int n,m,q;
vector<pii> way[maxn];
int open[maxn];
vector<pii> edge[maxn];
int res;

int get(int x, int val) {
    int l = 0, r = edge[x].size()-1, mid, pos = -1;
    while(l<=r) {
        mid = (l+r)/2;
        if(edge[x][mid].X <= val) {
            pos = mid;
            l = mid+1;
        }
        else r = mid-1;
    }
    if(pos==-1) return 0;
    return min(val, edge[x][pos].Y);
}

void solve(int u, int last, int cur) {
    if(cur==0) return ;
//    printf("solve %d : %d\n",u,cur);
    res++;
	for(auto t : way[u]) {
        int v = t.X, id = t.Y;
		if(v==last) continue;
		solve(v,u,get(id,cur));
	}
}

int main() {
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<n;i++) {
		int u,v; scanf("%d%d",&u,&v);
		way[u].push_back({v,i});
		way[v].push_back({u,i});
	}
	for(int i=1;i<=m;i++) {
		int x; scanf("%d",&x);
		if(!open[x]) open[x] = i;
        else {
            edge[x].push_back({open[x],i-1});
            open[x] = 0;
        }
	}
	for(int x=1;x<n;x++) {
        if(open[x]) {
            edge[x].push_back({open[x],m});
        }
	}
	for(int i=1;i<=q;i++) {
		int x; scanf("%d",&x);
		res = 0;
        solve(x,0,m);
        printf("%d\n",res);
	}
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&m,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~
synchronization.cpp:44:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u,v; scanf("%d%d",&u,&v);
            ~~~~~^~~~~~~~~~~~~~
synchronization.cpp:49:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d",&x);
          ~~~~~^~~~~~~~~
synchronization.cpp:62:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d",&x);
          ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 10 ms 9720 KB Output is correct
3 Correct 10 ms 9776 KB Output is correct
4 Correct 13 ms 9792 KB Output is correct
5 Correct 10 ms 9828 KB Output is correct
6 Correct 12 ms 9996 KB Output is correct
7 Correct 23 ms 10828 KB Output is correct
8 Correct 20 ms 11036 KB Output is correct
9 Correct 21 ms 11328 KB Output is correct
10 Correct 147 ms 20044 KB Output is correct
11 Correct 156 ms 22272 KB Output is correct
12 Correct 117 ms 23856 KB Output is correct
13 Correct 111 ms 26572 KB Output is correct
14 Correct 118 ms 28596 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 30988 KB Output is correct
2 Correct 81 ms 31988 KB Output is correct
3 Correct 79 ms 35916 KB Output is correct
4 Correct 71 ms 37112 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 37112 KB Output is correct
2 Correct 13 ms 37112 KB Output is correct
3 Correct 11 ms 37112 KB Output is correct
4 Correct 11 ms 37112 KB Output is correct
5 Correct 12 ms 37112 KB Output is correct
6 Correct 13 ms 37112 KB Output is correct
7 Correct 26 ms 37112 KB Output is correct
8 Correct 180 ms 37112 KB Output is correct
9 Correct 184 ms 39472 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 39472 KB Output is correct
2 Execution timed out 8055 ms 46276 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 46276 KB Output is correct
2 Correct 11 ms 46276 KB Output is correct
3 Correct 11 ms 46276 KB Output is correct
4 Correct 11 ms 46276 KB Output is correct
5 Correct 13 ms 46276 KB Output is correct
6 Correct 154 ms 46276 KB Output is correct
7 Correct 5800 ms 46276 KB Output is correct
8 Correct 181 ms 47212 KB Output is correct
9 Execution timed out 8006 ms 50060 KB Time limit exceeded
10 Halted 0 ms 0 KB -